RMQ Overkill

Range minimum query problems are getting more and more common everyday. I used to consider them as hard problems some years ago, but not anymore. So I decided to make this harder for everyone. Today you are given a sequence (with 0-based indexing) of non-negative integers which contains no more than 10000 elements and where each integer is less than 10. For each possible query (i, j) where ( 0 $\le$ i $\le$ j < 10000) [N is the size of the sequence], you have to find the minimum integer in that range, and add the minimums for all those queries together. When you are done that, mod the sum with 1000000007 and print.

Input

There will be multiple cases (no more than 120). You must read for cases until EOF.

For each case : First line, an integer N ( 1 $\le$ N $\le$ 10000), the size of the array. Second line, a string of N characters where i-th character denotes the i-th element of the sequence.

Output

For each case, one line containing an integer, R, the result described above.

Output Explanation

First case: all possible queries and there results are, (0, 0) = > 1, (0, 1) = > 1, (0, 2) = > 1, (1, 1) = > 4, (1, 2) = > 3, (2, 2) = > 3. So, R = 1 + 1 + 1 + 4 + 3 + 3 = 13.

Second case: all possible queries and there results are, (0, 0) = > 4, (0, 1) = > 1, (0, 2) = > 1, (1, 1) = > 1, (1, 2) = > 1, (2, 2) = > 3. So, R = 11.

Third case: all possible queries and there results are, (0, 0) = > 1, (0, 1) = > 1, (0, 2) = > 1, (1, 1) = > 2, (1, 2) = > 1, (2, 2) = > 1. So, R = 7.

Sample Input

Sample Output

13
11
7

Problem Setter: Pratyai Mazumder
Alternate Solution: Mohammad Hafiz Uddin