쿠키

해빈이와 준규는 쿠키를 좋아하는 쌍둥이 형제이다. 두 사람의 친구 진욱이는 해빈이와 준규에게 쿠키를 만들어 주는 것을 가장 좋아한다. 하지만 두 사람이 쿠키를 너무 빨리 먹는 것이 걱정되어, 오늘은 게임을 통해 쿠키를 천천히 먹는 방법을 알려 주려고 한다.

진욱이가 구운 쿠키는 N개이며, 각 쿠키에는 1번부터 N번까지 번호가 붙어 있다. 쿠키는 원형으로 놓여 있고, i번 쿠키는 i-1번 쿠키와 i+1번 쿠키 사이에 있다. 단, 1번 쿠키와 N번 쿠키도 서로 이웃한다.

쿠키의 맛은 모두 26가지이다. 각 맛은 알파벳 소문자 'a'부터 'z'까지 중 하나로 나타내며, 같은 문자는 같은 맛을 뜻한다.

해빈이와 준규는 5분마다 쿠키를 하나씩 먹는다. 진욱이가 쿠키 하나의 번호를 부르면, 두 사람은 그 번호의 쿠키를 찾은 뒤 그 쿠키는 먹지 않고 현재 그 쿠키의 양옆에 이웃한 두 쿠키를 하나씩 먹는다. 이 과정은 테이블에 남은 쿠키가 1개 또는 2개가 될 때까지 반복되고, 게임이 끝난 뒤 남은 쿠키는 진욱이가 먹는다.

하나의 게임은 진욱이가 부른 번호들을 순서대로 적은 길이 floor((N-1)/2)의 수열로 표현할 수 있다. 두 게임은 이 수열이 서로 다르면 다른 게임으로 본다.

몇 번의 게임을 진행한 뒤, 진욱이는 두 사람이 게임 도중 싸울 수 있다는 사실을 알게 되었다. 한 번에 먹는 두 이웃 쿠키의 맛이 서로 다르면 두 사람은 누가 어떤 쿠키를 먹을지 정하지 못해 싸우게 된다.

진욱이는 두 사람이 싸우지 않도록 게임을 진행하려고 한다. 쿠키 N개의 맛이 원형 순서대로 주어질 때, 두 사람이 싸우지 않게 게임을 진행하는 방법의 수를 구하시오. 방법의 수가 매우 클 수 있으므로 10007로 나눈 나머지를 출력한다.

첫째 줄에 쿠키의 수 N (3 <= N <= 100)이 주어진다.

둘째 줄에는 1번부터 N번까지의 순서대로 각 쿠키의 맛을 나타내는 길이 N의 문자열이 주어진다. 문자열은 알파벳 소문자 'a'부터 'z'까지로만 이루어진다.

해빈이와 준규가 싸우지 않게 게임을 진행하는 방법의 수를 10007로 나눈 나머지를 출력한다.