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
110
111
112
113
114
#include <bits/stdc++.h>

using namespace std;
typedef vector<int> VI;
typedef unsigned long long LL;
typedef vector<LL> VLL;
typedef pair<int,int> PI; 
typedef pair<LL,LL> PLL;
typedef unsigned long long ULL;
typedef pair<double,double> PD;

#define FOR(x, b, e) for(int x = b; x<= (e); x++)
#define FORD(x, b, e) for(int x = b; x>= (e); x--)
#define REP(x, n) for(int x = 0; x<(n); ++x)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(x) ((int)(x).size())

#define PB push_back
#define IN insert
#define ST first
#define ND second
#define INF 2000000011
#define MOD 1000000007

#define MAXSIZE 

int prog=2000000;
int n;

int main(){	//minimalizowanie pamieci w haszach i odpowiednie ustawienie ich, poniewaz nie znamy ich wlasciwej dlugosci
	
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n;
	if(n<=prog&&n!=0){
		string s;
		cin>>s;
		FOR(par,0,(n-1)/2){
			if(s[par]!=s[n-1-par]){
				cout<<"NIE";
				return 0;
			}
		}
		cout<<"TAK";
		return 0;		
	}
	else{	//kurde, czemu nie zauwazylem wczesniej tych bledow :(
		int param=5000;
		if(n!=0){
			FOR(i,1000,sqrt(n)){
				if(n%i==0)
					param=i;
			}
		}
		
		VLL pot;
		
		pot.PB(1);
		
		FOR(i,1,param-1)
			pot.PB((pot[i-1]*31LL)%MOD);
		
		VLL t_1;
		VLL t_2;
		LL pod_s1=0;
		LL pod_s2=0;
		
		char c;
		
		int dl=0;
		
		while(cin>>c){
			pod_s1=(pod_s1+(LL)(c-'a')*pot[dl%param])%MOD;
			pod_s2=(pod_s2+(LL)(c-'a')*pot[param-dl%param-1])%MOD;
			
			if(dl%param==param-1){
				t_1.PB(pod_s1);
				t_2.PB(pod_s2);
				pod_s1=0;
				pod_s2=0;
			}
			dl++;
		}
		if((dl-1)%param!=param-1){
			t_1.PB(pod_s1);
			t_2.PB(pod_s2);	
		}
		
		
		LL stala=1;
		pod_s1=0;
		REP(I,SIZE(t_1)){
			pod_s1=(pod_s1+t_1[I]*stala)%MOD;
			stala=(stala*pot[param-1]*31LL)%MOD;
		}
		pod_s1=(pod_s1*pot[(param-dl%param)%param])%MOD;
		
		stala=1;
		pod_s2=0;
		FORD(I,SIZE(t_2)-1,0){
			pod_s2=(pod_s2+t_2[I]*stala)%MOD;
			stala=(stala*pot[param-1]*31LL)%MOD;			
		}


		
		if(pod_s1==pod_s2)
			cout<<"TAK";
		else
			cout<<"NIE";
		
	}
	
	return 0;
}