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 ≤ i ≤ 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 ≤ N ≤ 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 3 143 3 413 3 121 Sample Output 13 11 7