A. Anton's ABCD
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

It is well-known that Anton Trygub likes setting problems about strings with the characters ABC in them. And he likes it even more when we are allowed to do operations on the string. To honour him, but also to improve further on his problems, here is a problem about a string with the characters ABCD in it. You are given a string consisting of the characters ABCD. How many distinct strings can you make, applying the following operation zero or more times?

  • Take a substring of length $$$4$$$, that is a cyclic shift of ABCD, and cyclic shift it to the left or right by $$$1$$$. (The cyclic shifts of ABCD are BCDA, CDAB and DABC.)
Because this number can be huge, please output it modulo $$$10^9+7$$$
Input

The first and only line of input contains the string $$$S$$$, ($$$1 \leq |S| \leq 2000$$$)

Output

Print a single line of output with one integer, the number of distinct strings that can be made using the operation repeatedly, modulo $$$10^9+7$$$.

Examples
Input
DABC
Output
4
Input
AABBCCDD
Output
1
Input
ABCDABCD
Output
52
Note

In the first example, the string is a cyclic shift of ABCD itself, and so within $$$2$$$ operations, we can get all cyclic shifts of this string, of which there are $$$4$$$.

In the second example, no move is possible in the beginning, so there's only one distinct string you can make.