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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
#define LL long long
using namespace std;

const LL MOD1 = 1000000021;
const LL MOD2 = 10007;

const LL DIV1 = 558583118;
const LL DIV2 = 4799;
const LL P = 367;

LL p11 = 1;
LL p12 = 1;
LL p21 = 1;
LL p22 = 1;

char c;
int n;

int main(){
    cin >> n;
    n = 0;
    for(int i = 1; i < 20000000; i++){
        p21 *= P;
        p21 %= MOD1;
        p22 *= P;
        p22 %= MOD2;
    }

    LL h11 = 0;
    LL h21 = 0;
    LL h12 = 0;
    LL h22 = 0;
    while( cin >> c ){
        h11 += (c * p11) % MOD1;
        h11 %= MOD1;
        h12 += (c * p12) % MOD2;
        h12 %= MOD2;
        h21 += (c * p21) % MOD1;
        h21 %= MOD1;
        h22 += (c * p22) % MOD2;
        h22 %= MOD2;

        p11 *= P;
        p11 %= MOD1;
        p12 *= P;
        p12 %= MOD2;
        p21 *= DIV1;
        p21 %= MOD1;
        p22 *= DIV2;
        p22 %= MOD2;
        n++;
    }

    p11 = 1;
    p12 = 1;
    for(int i = 1; i <= 20000000 - n; i++){
        p11 *= P;
        p11 %= MOD1;
        p12 *= P;
        p12 %= MOD2;
    }

    h11 *= p11;
    h11 %= MOD1;
    h12 *= p12;
    h12 %= MOD2;

    if(h11 == h21 && h12 == h22)
        cout << "TAK\n";
    else
        cout << "NIE\n";

}