Problem Description

Pty has a string s and a dictionary.

There are m words in the dictionary. Each word $t_i$ has its value $w_i$.

Define function $f(s,l,r)=$$\sum_{i=1}^m$$occur(s,l,r,t_i)*w_i$ , where $occur(s,l,r,t_i)$ is the number of occurrences of string $t_i$ in s[l...r]

The interest value of string s is $\sum_{l=1}^{\mid s \mid}$$\sum_{r=l}^{\mid s \mid}$$f(s,l,r)^5$

Pty wants to know the interest value of string s.

Since the answer might be very large, print the answer modulo $10^9$ + 7.

Input

The first line of input contains a integer T(1 ≤ T ≤ 11), the number of test cases.

For each case, the first line of input contains a string s (1 ≤$\mid s \mid$≤ 5×$10^5$).

The second line contains a integer m(0 ≤ m ≤ 5×$10^5$).

There are m lines next. The $i^{th}$ line contains a string ti and a integer $w_i$(0 ≤ $\sum_{i=1}^m \mid t_i \mid$ ≤ 5×$10^5$ , 1 ≤$w_i$≤ $10^9 + 7$).

It’s guaranteed that s,$t_i$ are non-empty strings.

Output

For each test case, print the interest value of string s, modulo $10^9$ + 7 in one line.

1
whkfqbw
3
h 3
hkfq 2
qb 2

75128