405210: GYM101845 G Generating Texts

Lucko is a greedy boy that is looking for ways to gain some money, one easy way he has found is to invest in bets on different lotteries, but he knows that the probability of winning a lottery is really low, for this reason he decides to play on a new lottery called UN-lotto.

To play UN-lotto one chooses a string of length m, then the lottery generates a string of length n (n ≥ m) randomly, both strings are formed only by lower-case letters from the english alphabet. You win if the string you have chosen is a subsequence of the generated text by UN-lotto.

Formally, for a string s = s₁s₂...s_n we say that s_a1s_a2...s_am is a subsequence of s of length m if 1 ≤ a₁ < a₂ < ... < a_m ≤ n. For example, suppose that n = 4 and m = 3 and Lucko chooses the string abc, some of the winning generated strings for him would be abcb, abbc and abzc, and some of the losing generated strings would be acba, azbz and zzzz

Good news for Lucko, information about this lottery has been leaked:

• The text is generated taking each letter randomly from a probability distribution.
• The selection of the letter for each position in the text is independent.
• The probability distribution of the letters was also leaked.

Lucko has already chosen his string to play UN-lotto, help him using the leaked information to tell him which is his probability P / Q of winning. As Lucko only likes low integer numbers calculate the probability modulo 10⁹ + 7, i.e., calculate

The first line of input contains 2 numbers n and m (1 ≤ m ≤ n ≤ 5000) — the length of the string generated by UN-lotto and the length of the string chosen by Lucko respectively.

The second line of input contains s — the string chosen by Lucko.

Next 26 lines contains each a pair of integers separated by spaces, i.e. the i-th line contains p_i, q_i, where corresponds to the probability of taking the i-th letter, being a the first letter, b the second letter and so on. For every i = 1, ..., 26, 0 ≤ p_i ≤ 1000, 1 ≤ q_i ≤ 1000 and p_i / q_i is an irreducible fraction.

It is guaranteed that .

Output one integer — the probability modulo 10⁹ + 7 of Lucko winning UN-lotto with the string s.

5 1
a
1 1
0 1
... 24 more lines ...

1

5 3
aaa
1 2
1 2
0 1
... 23 more lines ...

500000004