SP7023 KOLACI - Cookies

Darko and Marko are twins and they love to eat cookies. Their grandma Mara loves to bake cookies, but she doesn't like the fact that Darko and Marko eat them too fast. To teach her grandsons to eat slower, Mara turned it into a game. Mara will bake N cookies and assign them with integers 1 to N. Then she will arrange them in a circle such that each cookie i is between to cookie i−1 and i+1 except for cookies 1 and N that are neighbors. Mara knows a recipe for 26 different types of cookies. We will denote a cookie type with lower case english letters 'a' to 'z'. Darko and Marko will each get one cookie every 5 minutes. Mara will say one integer out loud. Darko and Marko will search for a cookie with this number, but will eat two neighboring cookies. This procedure is repeated until one or two cookies are left on the table. Then the game ends and Mara eats the remaining cookies.  The game can be represented with a sequence of (N−1) div 2 integers that Mara said out loud. For example, the illustrations above can be represented with a sequence (4, 8, 6). Two games are considered different if their respective sequences are different. After a few games Mara noticed that Marko and Darko often fight during the game. In fact, they fight every time when the two neighboring cookies are of different types because they can't decide which one will get which cookie. Mara decided to count the number of ways to play a game in a way to avoid such situations. Given a cookie type for each of N cookies, write a program that will calculate the number of ways to play a game such that Darko and Marko will not fight. This number can get very large, so output the remainder of division by 10007 instead.

The first line contains one integer N (3 The second line contains a sequence of N lower case english letters, types of cookies in order they are arranged in a circle.

Output a single integer, the total number of ways to play a game that will prevent Darko and Marko from fighting modulo 10007.