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
#include <cmath>
#include <ctime>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cctype>

using namespace std;

unsigned int prime = 2147483549; // little less than 2^31

int main()
{
        srand(time(NULL));

        int n;
        char c;
        unsigned long long a1, a2;
        unsigned long long ap1, ap2;
        unsigned long long r1, r2;
        unsigned long long f1, f2;

        scanf("%d\n", &n);
        a1 = rand() % 1000000000+2;
        a2 = rand() % 1000000000+2;

        scanf("%c", &c);
        r1 = f1 = ((c-'a')*a1) % prime;
        r2 = f2 = ((c-'a')*a2) % prime;

        ap1 = a1;
        ap2 = a2;

        while(1) {
                if (scanf("%c", &c) != 1) {
                        break;
                }
                if (!islower(c)) {
                        break;
                }
                c = c - 'a';
                ap1 = (ap1*a1) % prime; ap2 = (ap2*a2) % prime;
                f1 = (f1 + c*ap1) % prime; f2 = (f2 + c*ap2) % prime;
                r1 = ((r1 + c) * a1) % prime; r2 = ((r2 + c) * a2) % prime;
        }
/*
        printf("f1=%llu\n", f1);
        printf("r1=%llu\n\n", r1);

        printf("f2=%llu\n", f2);
        printf("r2=%llu\n\n", r2);
*/

        if ((f1 == r1) && (f2 == r2)) {
                printf("TAK\n");
        } else {
                printf("NIE\n");
        }

        return 0;
}