
ZOJ Problem Set  3813
There is a digit string S with infinite length. In addition, S is periodic and it can be formed by concatenating infinite repetitions of a base string P. For example, if P = 3423537, then S = 3423537342353734235373423537... Let's define the alternating sum on substrings of S. Assume S_{l..r} is a substring of S from index l to index r (all indexes are 1based), then the alternating sum of S_{l..r} is: G(l, r) = S_{l}  S_{l+1} + S_{l+2}  ... + (1)^{rl}S_{r}
For example, S_{2..10} = 423537342, then G(2, 10) = 4  2 + 3  5 + 3  7 + 3  4 + 2 = 3. Now, you are given the base string P and you have to do many operations. There are only two kinds of operations:
For each second operation, you should output the sum modulo 10^{9} + 7. InputThere are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case: The first line contains a digit string P (1 <= length(P) <= 100000). The second line contains an integer Q (1 <= Q <= 100000) indicating the number of operations. Each of the following Q lines is an operation in such format:
OutputFor each "2 l r" operation, output an integer, indicating the sum modulo 10^{9} + 7. Sample Input2 324242 4 2 1 1 2 1 4 1 3 7 2 3 4 324242 6 2 1 1 1 3 7 2 2 4 1 3 4 2 7 10 2 1 30 Sample Output3 20 14 3 8 20 870 Author: LIN, Xi Source: The 2014 ACMICPC Asia Mudanjiang Regional First Round 