타카하시의 카드 게임

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

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

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

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

두 번째 줄에 길이 $n$의 문자열이 주어집니다. $i$번째 문자는 $i$번 카드에 적힌 문자입니다.

문제의 정답을 출력하세요.

$2 \le n \le 500\,000$

팰린드롬은 앞으로 읽어도 뒤로 읽어도 같은 문자열입니다.