There was a small pond besides a road in Babylon . There were N consecutive stones in that small pond . Each stone had a no 1 , 2 , or 3 written on it .

At the farther end of the pond lived a frog with his family . In order to search for food the frog family crossed the pond by jumping on stones as shown in the image .

A Professor passing by the road observed the frog's motion and found that each Frog performed a sequence of steps to reach the end. Each step was lead in the positive direction, that is, if current position of the frog was stone k, the next jump will take frog to one of the stones k+1 through N stones ,inclusive . Jumps made by the frog can be short/long . However, longer jumps are costly as jump of length l required work of about pow(l,2) .

Additionally, Frog's jumped on the stones in a cyclic order 1,2,3, 1,2,3 and so on . ... That is, Frog started on the 1st stone with no 1, made a jump to a stone with no 2 on it , from there to a stone with no 3 , and so on, always repeating no's 1, 2, and 3 in a cycle.

Notes :

* The 1st stone has a no 1 written on it by default .

* There wouldn't be any such cases in which the frog's cant cross the pond .

Professor was impressed by the clever Frogs and thus Transformed the situation into a computing problem . He wanted his student's to print the minimum cost to reach the last stone .

Input

You would be a given string S with value of each stone .

Output

Print Minimal cost of reaching the end Mod 1e9+7 . ( Following an Optimal Strategy )

Constraints

1<=L<=4000