Takahashi's Card Game

Interview

Time limit1sMemory limit512 MB

Summary

Count the subsets of at least 2 cards where every proper nonempty draw, in any order, forms a palindrome, modulo 10^9 + 7.

Level: Medium4 of 10
Topics: Math, Combinatorics, String, Hash map
Solved: No attempts yet

Problem

Cards numbered 1 through $n$ are given, for $n$ distinct cards in total. Each card has one letter written on it, either lowercase or uppercase. Gahee picks at least 2 of these cards and puts them into a random box. Takahashi performs the following actions in order.

Draw one or more cards from the random box. After this action, at least one card must remain in the box.
Arrange the drawn cards in the order they were drawn to form a string.

If the resulting string is a palindrome, Gahee wins. Otherwise, Takahashi wins. Print the number of ways to put cards into the random box so that Gahee always wins, modulo $10^{9} + 7$ .

Input

The first line contains the number of cards $n$ .

The second line contains a string of length $n$ . The $i$ -th character is the letter written on card $i$ .

Output

Print the answer to the problem.

Constraints

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

Hint

A palindrome reads the same forwards and backwards.

Examples2

Example 1
Input
```
6
aabbaa
```
Expected output
```
20
```
Example 2
Input
```
2
mm
```
Expected output
```
1
```