In this time, Yunyan made full preparations and launched a global magic, making all the creatures asleep, so that he could loot magic power from everyone. But to his surprise, the Abyss AI——now named as Xingyue was here and it brought Miming to fight against him.

Even though with the help of Xingyue, Miming is in bad situation. At this point, the Abyss Cycle started ahead of schedule, so Yunyan's power quickly shrinks. Miming seizes the opportunity and defeats him. After stopping the global magic, everyone is awake again.

To compensate for the loss of people caused by global magic, Yunyan'd play a string game with Miming. If Miming wins, Yunyan'd give everyone 1437 money. If Yunyan wins, he'd only give everyone 580 money.

There has a string S consists of lowercase letters only. The length of S is n . We use $Si to stands for the i-th letter of the string. And S{l,r} stands for the substring of Sl, S{l+1}, \cdots, Sr . Specially, if l > r then S{l,r} is an empty string. Define the prefix function \pi(i) as the max integer j\in[0,i) satisfying S{1,j}=S{i-j+1,i}$ . For example, if S=ababac , then \pi(1)=\pi(2)=0,\pi(3)=1,\pi(4)=2,\pi(5)=3,\pi(6)=0 .

Two players Yunyan, Miming have a game on the string S and Yunyan goes first. At first, for every index i\in[1,n] ,if \pi(i)\neq0 then it's unlocked, otherwise it's locked. Each turn, the player can choose an unlocked index i and then lock all the index j\in(i-\pi(i),i] . The player who cannot choose any index fails the game, and the other player wins. If both players play with optimal strategies, please find out who wins the game.

Input the first line with one integer n(1\le n\le10^6) .

Input the second line with one string S consisting of n lowercase letters.

If Yunyan wins, output 580 . If Miming wins, output 1437 .

In the first example, Yunyan can choose i=5 and lock 3,4,5 . Then Miming has no choice.

In the second example, if Yunyan first choose i=8 and lock 7,8 . Then it can be proved that no matter how Miming choose, Miming will always lose.

In the third example, it can be proved that no matter how Yunyan choose, Yunyan will always lose.