32781번 - 타카하시의 카드 게임

문제

1ドル$번 카드부터 $n$번 카드까지 서로 다른 $n$개의 카드가 있습니다. 각각의 카드에는 알파벳 소문자와 대문자 중 하나의 문자가 적혀 있습니다. 가희는 이 중 2ドル$개 이상의 카드를 뽑아서 랜덤 상자에 넣었습니다. 타카하시는 다음 행동을 아래 순서대로 수행합니다.

• 랜덤 상자에서 카드를 1ドル$개 이상 뽑습니다. 이 행동을 수행한 후, 랜덤 상자에는 카드가 적어도 하나 이상 남아 있어야 합니다.
• 뽑은 카드들을 뽑은 순서대로 나열해 문자열을 만듭니다.

만들어진 문자열이 팰린드롬이면 가희가, 그렇지 않으면 타카하시가 승리합니다. 가희가 항상 승리하도록 카드를 뽑아서 랜덤 상자에 넣는 가짓수를 10ドル^{9} + 7$로 나눈 나머지를 출력해 주세요.

입력

첫 번째 줄에 카드의 수 $n$이 주어집니다.

두 번째 줄에 길이 $n$의 문자열이 주어집니다. $i$번째로 주어지는 문자는 $i$번 카드에 적혀 있는 문자를 의미합니다.

출력

문제의 정답을 출력해 주세요.

제한

• 2ドル ≤ n ≤ 500,000円$

힌트

팰린드롬이란 앞으로 읽어도, 뒤로 읽어도 같은 문자열을 의미합니다.