Cookies

Haebin and Jungyu are twin brothers who love cookies. Their friend Jinuk likes nothing more than baking cookies for them. Because they eat cookies too quickly, Jinuk wants to teach them to eat more slowly by turning it into a game.

Jinuk baked N cookies, numbered from 1 to N. The cookies are arranged in a circle. Cookie i is between cookies i-1 and i+1, and cookies 1 and N are also adjacent.

There are 26 possible cookie flavors. Each flavor is represented by one lowercase English letter from 'a' to 'z'; equal letters mean equal flavors.

Haebin and Jungyu each eat one cookie every 5 minutes. When Jinuk calls the number of a cookie, they find that cookie, leave it on the table, and eat the two cookies currently adjacent to it. This continues until only 1 or 2 cookies remain on the table. After the game ends, Jinuk eats the remaining cookies.

A game can be represented by the sequence of numbers Jinuk calls, whose length is floor((N-1)/2). Two games are different if these sequences are different.

After playing several times, Jinuk noticed that the twins may fight during the game. If the two neighboring cookies eaten in one turn have different flavors, they cannot decide who should get which cookie and start fighting.

Jinuk wants to play the game so that they never fight. Given the flavors of the N cookies in circular order, count the number of possible games with no fight. Since the answer can be very large, output it modulo 10007.

The first line contains an integer N (3 <= N <= 100), the number of cookies.

The second line contains a string of length N describing the flavors of cookies 1 through N in order. The string consists only of lowercase English letters from 'a' to 'z'.

Output the number of ways to play the game without Haebin and Jungyu fighting, modulo 10007.