#include <iostream>
using namespace std;

int main() {

    int arr[4] = {10, 670, 55252, 4816030};
    short m;

    cin >> m;
    cout << arr[m / 2 - 1];
    return 0;
}

//hey; can you guess how i got these values?(think of the simplest solution)

Edited by author 15.02.2013 04:31

Nothing funny.

if we are not too creative to calculate this on paper and there is no forum to take solution just do backtracking it works fine 1 second and something
#include <iostream>
using namespace std;
int x[10], n, cont = 0;
void back(int k)
{
    if(k == n)
    {
        int s1 = 0, s2 = 0;
        for(int i = 0; i < n / 2; i++)
        {
            s1 += x[i];
        }
        for(int i = n / 2; i <= n; i++)
        {
            s2 += x[i];
        }
        if(s2 == s1)
            cont++;
    }
    else
        for(int i = 0; i <= 9; i++)
        {
            x[k] = i;
            back(k + 1);
        }
}
int main () {
    cin >> n;
    back(0);
    cout << cont;
    return 0;
}