Given $n$ strings $s_i$ and $m$ strings $t_j$. Let $f(i, j, k, l)$ denote the number of occurrences of $s_i + t_j$ as a substring of $s_k + t_l$, where $a + b$ denotes the concatenation of string $b$ to the end of string $a$. Calculate the value of:

$$\sum_{i=1}^{n} \sum_{j=1}^{m} \sum_{k=1}^{n} \sum_{l=1}^{m} f(i, j, k, l)$$

Since the answer can be very large, output the value modulo $10^9 + 7$.

For strings $a, b$, the string $a + b$ represents the concatenation of $b$ directly after $a$. For example, if string $a$ is abc and string $b$ is ab, then $a + b$ is abcab.

For non-empty strings $a, b$, if $b$ is obtained by removing some prefix and some suffix (possibly empty) from $a$, then $b$ is called a substring of $a$. For example, for the string abcd, the strings a, bcd, and bc are all substrings of this string, while the strings acd and bd are not.

Input

The first line contains two integers $n$ and $m$.

The next $n$ lines each contain a string $s_i$ consisting only of lowercase English letters.

The next $m$ lines each contain a string $t_j$ consisting only of lowercase English letters.

Output

Output a single integer representing the answer modulo $10^9 + 7$.

Examples

Input 1

2 3
a
ba
b
bb
ab

Output 1

14

Examples 2

See string/string2.in and string/string2.ans in the contestant's directory. This example satisfies the constraints for test cases $3 \sim 6$.

Examples 3

See string/string3.in and string/string3.ans in the contestant's directory. This example satisfies the constraints for test cases $9 \sim 12$.

Examples 4

See string/string4.in and string/string4.ans in the contestant's directory. This example satisfies the constraints for test cases $13 \sim 20$.

Constraints

For all test data, it is guaranteed that: $1 \le n, m \le 10^5$, $1 \le |s_i|, |t_j| \le 10^6$, and $\sum |s_i|, \sum |t_j| \le 10^6$.

Special Property A: All $s$ strings contain only one type of letter, and all $t$ strings contain only another type of letter different from $s$.