I-古老的打字机_“科大讯飞杯”第18届上海大学程序设计联赛春季赛（校内赛）

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

Compute 在他的家里找到了一个打字机，他想要用这个打字机来打字，但是这个打字机实在是太古老了，以至于它根本就无法打出正确的内容。
给定 n 个由小写字母组成的字符串 $s_1, s_2, \ldots s_n$ ，每个字符串有一个价值 $v_i$ 。
现在 Compute 会用这个打字机来打字，他会敲击打字机 m 次，得到字符串 t。其中，每次敲击会等概率地输入一个小写字母或者退格（Backspace）。
退格的作用是把当前得到的字符串的最后一个字符删除。特别地，如果当前字符串是空串，退格后仍为空串。
定义他最后所得到的字符串的价值为：每个串 $s_i$ 在得到的串 t 中的出现次数 $c_i$ 与价值 $v_i$ 的乘积。即 $\displaystyle\sum_{k = 1} ^ n \sum_{i = 1} ^ {|t|} \sum_{j = i} ^ {|t|} v_k \cdot [s_k = \text{substr}(t, i, j)]$
其中 $\text{substr}(t, i, j)$ 表示 t 串从第 i 个字符到第 j 个字符组成的子串；
艾佛森括号 $[\text{expr}] = \begin{cases} 1 & \text{expr 为真} \\ 0 & \text{expr 为假} \end{cases}$ 。
Compute 想要知道他得到的字符串价值的期望是多少。
可以证明这个期望的 $27 ^ m$ 倍是一个整数，因此你只需要求出它的 $27 ^ m$ 倍对 $10 ^ 9 + 7$ 取模后的结果。

输入描述:

第一行包含两个整数 n, m ()， 中间以空格分隔，分别表示字符串的个数和 Compute 的敲击次数。
接下来 n 行，每行包含一个由小写字母组成的字符串  ()和一个整数  ()，中间以空格分隔，分别表示给定的字符串和它的价值。
输入保证 。

输出描述:

在一行输出一个整数，表示 Compute 打出的随机字符串价值的期望的  倍对  取模后的结果。

示例1

输入

复制

1 1
a 1

输出

复制

示例2

输入

复制

2 2
a 1
aa 2

输出

复制

示例3

输入

复制

3 3
a 1
aa 2
aaa 3

输出

复制

备注:

对于第一个样例，共有 27 种情况，只有 a 具有 1 的价值，因此答案为 ，输出 1；
对于第二个样例，共有  种情况，其中 aa 的价值为 4，ab, ba ... az, za 的价值为 1，a （退格 + a）的价值为 1，因此答案为 ，输出 55。