Redaksiya

Let $a [i] [j]$ represent the number of ways in which Hodja Nasreddin can reach the cell $(i, j)$ from $(1, 1)$ .

Let $b [i] [j]$ represent the number of ways in which donkey can reach the cell $(i, j)$ from $(n, n)$ .

The number of ways in which Hodja and the donkey can meet at cell $(i, j)$ is equal to $a [i] [j] \cdot b [i] [j]$ .

To get the answer, it remains to compute the sum of products modulo $9929$ :

i = 1 \sum n j = 1 \sum n a_{ij} \cdot b_{ij} m o d 9929

Example

Let's build the arrays for $n = 3$ :

i = 1 \sum 3 j = 1 \sum 3 a_{ij} \cdot b_{ij} = (6 + 3 + 1) + (3 + 4 + 3) + (1 + 3 + 6) = 30

Algorithm realization

Declare the arrays.

#define MAX 55
#define MOD 9929
int a[MAX][MAX], b[MAX][MAX];

Read input value of $n$ .

scanf("%d", &n);
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));

Compute the values of the cells in arrays $a$ and $b$ .

a[1][1] = 1;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
  a[i][j] = (a[i][j] + a[i - 1][j] + a[i][j - 1]) % MOD;

b[n][n] = 1;
for (i = n; i >= 1; i--)
for (j = n; j >= 1; j--)
  b[i][j] = (b[i][j] + b[i + 1][j] + b[i][j + 1]) % MOD;

In the variable $res$ , find the number of ways in which Hodja and the donkey can meet.

res = 0;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
  res = (res + a[i][j] * b[i][j]) % MOD;

Print the answer.

printf("%d\n", res);