1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
using namespace std;
#define M   12357
int main() {
    int n;
    scanf("%d", &n);
    if (n % 2 == 1) {
        printf("0\n");
    } else {
        int a4, a2 = 3, a0 = 1;
        for (int i = 4; i <= n; i += 2) {
            a4 = ((a2 << 2) - a0 + M)% M;
            a0 = a2, a2 = a4;
        }
        if (n == 2) {
            printf("%d\n", a2);
        } else {
            printf("%d\n", a4);
        }
    }
    return 0;
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX