Pinocchio

Interview

Time limit2sMemory limit512 MB

Summary

Count the ordered 4-tuples of distinct positions in S whose letters are A, C, G, T in some fixed assignment.

Level: Easy3 of 10
Topics: Combinatorics, Math
Solved: No attempts yet

Problem

A human chromosome is made of four bases, written with the four letters A, C, G, and T. Junseo decided to build a Pinocchio that will serve his shifts for him.

Junseo has a base sequence $S$ of length $L$ . Pulling one A, one C, one G, and one T out of that sequence and synthesizing them builds one Pinocchio. Two bases with the same letter behave a little differently depending on where they sit in the sequence. Two Pinocchios are therefore the same only when all four positions they came from are the same, and they differ as soon as one position differs. Find how many kinds of Pinocchio Junseo can build.

Input

The first line contains the length of the base sequence, $L$ ( $1 \le L \le 10^6$ ). The second line contains a string $S$ of length $L$ . Every character of $S$ is one of A, C, G, and T.

Output

Print, on one line, the number of kinds of Pinocchio modulo $10^9 + 7$ .

Examples3

Example 1
Input
```
5
AACGT
```
Expected output
```
2
```
Example 2
Input
```
4
ACGT
```
Expected output
```
1
```
Example 3
Input
```
1
G
```
Expected output
```
0
```