给出一个长度为 的小写字符串 ，第 个位置有权值 。 现在，一共进行 次查询，对于一次查询给出的区间 ，记模式串 、 为字符串 在字符串 中出现的次数（允许重叠）。定义连续非空子串 的价值为： 。 求 的所有子串的价值和。由于答案可能很大，请将答案对 取模后输出。

输入描述:

第一行输入两个整数 ，表示字符串长度、查询次数。第二行输入一个长度为 ，仅由小写字母构成的字符串 。第三行输入 个整数 ，表示第 个位置的权值。此后 行，第 行输入两个整数 ，表示第 次查询的区间。

输出描述:

对于每一次询问，新起一行输出一个整数，表示原字符串所有子串的价值和对 取模后的结果。