Return to Question

Given an n-digit positive integer, count and print the number of subsequences formed by concatenating the given number's digits that are divisible by 8. As the result can be large, print the result modulo 10⁹ + 7.

Input Format

The first line contains an integer denoting n.

The second line contains a string describing an n-digit integer.

Constraints

· 1 ≤ n ≤ 2 x 10⁵

Output Format

Print a single integer denoting the count of subsequences of the given number that are divisible by 8, modulo 10⁹ + 7.

Sample Input 0

3

968

Sample Output 0

3

Explanation 0

The numbers obtained from subsequences of 968 are 9,6,8,96,68,98 and 968. Three of these numbers (i.e., 968,96, and 8) are divisible by 8, so we print the value of 3 mod (10⁹ + 7) = 3 as our answer.

Given an n-digit positive integer, count and print the number of subsequences formed by concatenating the given number's digits that are divisible by 8. As the result can be large, print the result modulo 10⁹ + 7.

Input Format

The first line contains an integer denoting n.

The second line contains a string describing an n-digit integer.

Constraints

· 1 ≤ n ≤ 2 x 10⁵

Output Format

Print a single integer denoting the count of subsequences of the given number that are divisible by 8, modulo 10⁹ + 7.

Sample Input 0

3

968

Sample Output 0

3

Explanation 0

The numbers obtained from subsequences of 968 are 9,6,8,96,68,98 and 968. Three of these numbers (i.e., 968,96, and 8) are divisible by 8, so we print the value of 3 mod (10⁹ + 7) = 3 as our answer.

For second choice of including digit 6, Or we will include 6 in the subsequences, therefore, we have to iterate the remainder with nonzero values: 0 and 1. two numbers of 6 and 16, 6's remainder of module 8 is 6, and 16' remainder of 8 is 0. The row entry: 1, 0, 0, 0, 0, 0, 1, 0.

For second choice of including digit 6, we will include 6 in the subsequences, therefore, we have to iterate the remainder with nonzero values: 0 and 1. two numbers of 6 and 16, 6's remainder of module 8 is 6, and 16' remainder of 8 is 0. The row entry: 1, 0, 0, 0, 0, 0, 1, 0.

At first, the first digit of number 968 is 9, the possible subsequences of 9 is empty number(none is selected) and 9. So the remainders are 0 or 1, since 9 % 8 = 1.

Work on the next digit 6, so either the digit 6 is not included in the subsequences or is included in the sequence.

For first choice of excluding digit 6, we just copy the subsequences in last step, two numbers: 0 and 9, frequency table row entry: 1, 1, 0, 0, 0, 0, 0

For second choice of including digit 6, Or we will include 6 in the subsequences, therefore, we have to iterate the remainder with nonzero values: 0 and 1. two numbers of 6 and 16, 6's remainder of module 8 is 6, and 16' remainder of 8 is 0. The row entry: 1, 0, 0, 0, 0, 0, 1, 0.

So, combining the above two choices, second row frequency table 2, 1, 0, 0,0, 0, 1, 0.