D. Speedy Stamping
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Another event in Crapper and Co.'s office olympics is the stamp race, which works the following way. Each employee has four stamps – one marked T (for Thomas), one marked C (for Crapper), one marked TC (for Thomas Crapper), and one marked CC (for Crapper and Co).

Thomas has prepared a desired string composed of only T's and C's. The employee who writes out the desired string the fastest, given only the four stamps, is declared the winner.

Thomas pays his employees minimum wage and does not particularly care who wins the race. However, he is curious as to what strategies his employees will employ. Can you determine how many ways the given string can be created using only the four stamps?

(The order in which stamps are employed does not matter, only which stamp is used for each letter.)

Input

The first line contains a single string $$$S$$$, composed of uppercase T's and C's, representing the target string to be stamped. ($$$1 \le |S| \le 10^6$$$)

Output

Output a single integer, denoting the number of ways the target string can be created using only the four stamps. Because this number can be very large, output it modulo $$$10^9 + 7$$$.

Example
Input
TCC
Output
3
Note

In the first test case, we can generate the string "TCC" in exactly three ways:

  • [T][C][C]
  • [TC][C]
  • [T][CC]