409018: GYM103415 J Cafeteria

Class is over, and Dave is the first to rush into the cafeteria! There is a long table full of $$$n$$$ dishes in order, and the $$$i$$$-th dish is $$$a_i$$$. Dave wants to eat $$$m$$$ dishes, so he writes the name of the $$$m$$$ dishes on a slip of paper, and the $$$i$$$-th dish is $$$b_i$$$. Dave and his classmates start lining up from the beginning of the long table, and he will take the dish in front of him to his plate when he finds it exactly the same as the first remaining dish on his slip of paper and then crosses it out from the slip. The cafeteria is so crowded that Dave would sometimes not see the dish in front of him. At the same time, it is clearly impossible for Dave to turn back and pick up a dish that he had already gone by.

This happens every day during the $$$t$$$ days when Dave is in school, but the dishes that Dave wants to eat are always the same. However, on the $$$i$$$-th day in the crowded cafeteria, Dave can only see dishes $$$l_i$$$ to $$$r_i$$$ on the long table, and he wants to know the number of ways to satisfy his needs for each day. Two ways are considered different if there is at least one difference in the location where the dishes are taken.

The first line contains three integers $$$n$$$ ($$$1 \leq n \leq 2 \times 10^5$$$), $$$m$$$ ($$$1 \leq m \leq 30$$$), and $$$t$$$ ($$$1 \leq t \leq 10^6$$$).

The second line contains a string $$$a_i$$$ of length $$$n$$$, and the third line contains a string $$$b_i$$$ of length $$$m$$$. It is guaranteed that there are only lowercase characters.

In the next $$$t$$$ lines, each line contains two positive integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$).

The output is large, so you only need to print $$$1$$$ integer — The XOR sum of the $$$t$$$ integers.

The $$$i$$$-th integer is the number of ways for Dave to take dishes on the $$$i$$$-th day, taken modulo $$$10^9+7$$$.

8 2 3
abcabbcb
ab
1 5
1 7
3 8

5

In the sample:

For the first day, Dave have $$$3$$$ ways to take dishes.

For the second day, Dave have $$$5$$$ ways to take dishes.

For the third day, Dave have $$$3$$$ ways to take dishes.

So the XOR sum of them is $$$5$$$.