Problem N
Crypto Trouble

Mr. Krabs is a hardcore cryptocurrency and blockchain technology enthusiast. In a recent conference, he heard about a new cryptocurrency called ByteConn333ct, which promises a very high rate of return. He wants to invest in this cryptocurrency, but its unique conversion rate to Canadian dollars makes him a bit apprehensive.

Several steps are need to compute the value of $B$ ByteConn333ct dollars (guaranteed to be an integer) in Canadian dollars. First, treat $B$ as a string consisting of only digits. Next, define a subset $S$ of characters from $B$ “valid” iff the characters in $S$ can be concatenated together in some way to form a number with no leading zeros that is also divisible by $3$. Finally, the converted value in Canadian dollars is the number of “valid” subsets modulo ${10}^9+7$.

Since Mr. Krabs is already so rich from his successful fast food restaurant business, he has decided to dump all of his life’s saving into investing ByteConn333ct. Mr. Krabs can’t wait to find out what amazing returns he will get, so he has hire you to compute the value of $S$ ByteConn333ct dollars in Canadian dollars so that he celebrate in advance this amazing investment he has made.

Input

The first line of the input contains a single integer $1\le N\le 200000$. The second line of the input contains a single $N$-digit non-negative integer $S$ without leading zeros.

Output

Output the value of $S$ ByteConn333ct dollars in Canadian dollars (i.e. the number of valid subsets of $S$ modulo ${10}^9+7$).

3
361

3

2
11

0

4
3051

6