下课了，Dave 是第一个冲进食堂的人！有一张长桌子，上面按顺序摆放着 $n$ 道菜，第 $i$ 道菜是 $a_i$。Dave 想吃 $m$ 道菜，所以他在一张纸条上写下了这 $m$ 道菜的名字，第 $i$ 道菜是 $b_i$。Dave 和他的同学从长桌的起点开始排队，当他发现眼前的菜与他纸条上剩下的第一道菜完全相同时，他就会把眼前的菜拿到自己的盘子里，并在纸条上将其划掉。食堂非常拥挤，以至于 Dave 有时会看不到眼前的菜。同时，Dave 显然不可能转身去拿他已经走过去的菜。

在 Dave 上学的 $t$ 天里，每天都会发生这种情况，但 Dave 想吃的菜总是相同的。然而，在第 $i$ 天拥挤的食堂里，Dave 只能看到长桌上从 $l_i$ 到 $r_i$ 的菜，他想知道每天满足他需求的方法数。如果拿菜的位置至少有一个不同，则认为两种方法是不同的。

输入格式

第一行包含三个整数 $n$ ($1 \le n \le 2 \times 10^5$)，$m$ ($1 \le m \le 30$) 和 $t$ ($1 \le t \le 10^6$)。

第二行包含一个长度为 $n$ 的字符串 $a_i$，第三行包含一个长度为 $m$ 的字符串 $b_i$。保证只包含小写字母。

接下来的 $t$ 行中，每行包含两个正整数 $l_i$ 和 $r_i$ ($1 \le l_i \le r_i \le n$)。

输出格式

输出量较大，因此你只需要输出 1 个整数——这 $t$ 个整数的异或和。

其中第 $i$ 个整数是 Dave 在第 $i$ 天拿菜的方法数对 $10^9 + 7$ 取模后的结果。

样例

输入 1

8 2 3
abcabbcb
ab
1 5
1 7
3 8

输出 1

5

说明

在样例中：

• 对于第一天，Dave 有 3 种拿菜的方法。
• 对于第二天，Dave 有 5 种拿菜的方法。
• 对于第三天，Dave 有 3 种拿菜的方法。

因此它们的异或和为 5。