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
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
#include<iostream>
#define LICZBAMODULO 100000007
using namespace std;
char s[1000000];

long long potegi_31[30];
int potegi_2[30];

long long pot_szybkie(long long a, int n)
{
    long long w = 1;

    while(n>0)
    {
        if (n & 1 == 1) //jesli bit jest = 1
            w = (w * a) % LICZBAMODULO;
        a = (a * a) % LICZBAMODULO;
        //cout<<a<<" "<<w<<endl;
    n/=2; //skrócenie o jeden bit
    }
    return w;
}

void uzupelnij_potegi()
{
    int a=1;
    for(int i=0;a<=20000000;i++)
    {
        potegi_2[i]=a;
//         cout<<a<<" "<<pot_szybkie(31,a)<<endl;;
        potegi_31[i]=pot_szybkie(31,a);
        a*=2;
    }
}

long long jeszcze_szybsze_pot_liczby_31(int n)
{
        long long w = 1;
        for(int i=0;i<25;i++)
        {
            if(n & potegi_2[i])
                w = (w * potegi_31[i]) % LICZBAMODULO;
        }
        return w;
}


char c;
int c2;
int n;
int i=0;
int wynik=0;
long long hash1,hash2;
int main()
{
    ios_base::sync_with_stdio(false);
//     cout<<sizeof(s)<<endl;;
//     cout<<sizeof(potegi_2)<<endl;;
//     cout<<sizeof(potegi_31)<<endl;;
//     
    uzupelnij_potegi();
    cin>>n;
    if(n==0 or n>=2000000)
    {
        while(cin >> c)
        {
            
            hash1 = (hash1 * 31 + c-97)%LICZBAMODULO;
            hash2 = (hash2 + (c-97)*jeszcze_szybsze_pot_liczby_31(i))%LICZBAMODULO;
            //cout<<c<<" "<<c-97<<endl;
            i++;
        } 
        if(hash1==hash2)
            cout<<"TAK";
        else
            cout<<"NIE";
        return 0;
    }
    else
    {
        for(int i=0;i<n/2;i++)
        {
            cin>>s[i];
            
        }
        if(n & 1)
            {
                cin>>c;
//                 cout<<"pojedynczy "<<c<<endl;
            }
//         for(int i=0;i<n/2;i++)
//             cout<<s[i];
//         cout<<endl;
        for(int i=n/2-1;i>=0;i--)
        {
            cin>>c;
//             cout<<i<<" "<<s[i]<<" "<<c<<endl;
            if(s[i]!=c)
            {
                cout<<"NIE";
                return 0;
            }
            
        }
        cout<<"TAK"<<endl;
        return 0;
    }
    return 0;
}