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\leq N\leq 200\, 000$. 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$).
| Sample Input 1 | Sample Output 1 |
|---|---|
3 361 |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 11 |
0 |
| Sample Input 3 | Sample Output 3 |
|---|---|
4 3051 |
6 |
