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.

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 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 |