Problem Description

As we all know, computer uses binary code to compute. Each decimal digit can be represented by a string of 0/1:

Decimal  0  1  2  3  4  5  6  7  8  9
Binary  0  1  10  11  100  101  110  111  1000  1001

We are going to transfer all the integers from L to R, both inclusive, with each decimal digit to binary. For example, after transferring decimal integer 127 to our binary representation, we can get 110111, because 1 is 1, 2 is 10 and 7 is 111. Happily, we find that n continuous bits s[i] have values v[i] associated with them. For a decimal number, after transferring to binary, if s[i] appears in it for k times, the value of if will be added k*v[i]. Now we want you to calculate the sum of value for each integer from L to R.
Since the answer may be very large, you just need to output it mod 1000000007.

Input

The first line of the input contains a single integer T denoting the number of test cases.
For each test case, the first line contains a single integer n denoting the number of valuable continuous bits.
Then comes n lines, each line has a string s contains only 0 and 1 and an integer v denoting the value.
The last line has two integers L and R.

Output

For each test case, output a single integer—the sum of value for each integer from L and R.

1
2
010 2
101 3
1 20

6

Hint

T<=10
n<=100,length(s)<=100,val<=100
L<=R<=10^100