1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
#include <stdio.h>
#include <stdlib.h>
#define I unsigned long long int
// ajde 10 točk?
int x (int n, int idx, int vrs) {
if (vrs <= n)
return idx;
else
return idx + vrs - n;
}
I y (int n, int idx, int vrs) {
if (vrs <= n)
return vrs - idx;
else
return idx;
}
I grdo (int x, int y, int n, char * sat) {
if (sat[y*1024+x])
return 0;
I sum = 0;
if (x == n-1 && y == n-1)
return 1;
if (x < n-1 && y)
sum += grdo(x+1, y+1, n, sat);
if (x < n-1)
sum += grdo(x+1, y, n, sat);
if (y < n-1)
sum += grdo(x, y+1, n, sat);
return sum;
}
int main (void) {
char * sat = malloc(1024*1024);
char buf[255];
fgets(buf, 255, stdin);
int n = atoi(buf);
fgets(buf, 255, stdin);
int k = atoi(buf);
while (k--) {
fgets(buf, 255, stdin);
char * c = buf;
int vrs = strtol(c, &c, 10);
c++;
int idx = strtol(c, &c, 10);
sat[y(n, idx, vrs)*1024+x(n, idx, vrs)]++;
}
printf("%llu\n", grdo(0, 0, n, sat) % 1000000007);
}
|
