Limits 5s, 512 MB

Byang is the most famous detective of Dhaka City. He has just received a secret document regarding his latest case. He is wondering whether this document will help him catch the infamous Kolabyang, a name terrorizing the whole Kua city! Byang checked the document quickly, and found that there is no characters in it other than numbers and alphabets. Byang also has a pattern P in his hand. He figured the pattern out after examining hundreds of files, abandoned hard drives, anonymous tips and what not. Byang thinks if his pattern occurs in the secret document, the whole document becomes relevant to this case. So he needs to find out whether the pattern has occurred at least once in the secret document.

But finding patterns in a large document is difficult. Besides, Byang’s pattern has some special properties. His pattern includes some non-overlapping sub-strings that may be ignored while searching. We can call these non-overlapping sub-strings as optional sub-patterns. More formally, if there are two optional sub-patterns P[x...y]P[x...y] and P[a...b]P[a...b] are included in our pattern, then either y<ay < a or b<xb < x. The remaining non-overlapping sub-patterns are called mandatory sub-patterns. The mandatory sub-patterns must be present, in given order, to prove the relevance of that document to Byang’s case.

For example, if the original pattern is P = “ABCADA”, text is T = “ABCXYADGHA” and two optional sub-patterns are P[2...3] = “BC” and P[4...5]=”AD”, then “AA”, “ABCA”, “AADA” and “ABCADA” are valid matches for P in T. The 7 matches of P in T can be found in following way, ABCXYADGHA, ABCXYADGHA, ABCXYADGHA, ABCXYADGHA, ABCXYADGHA, ABCXYADGHA and ABCXYADGHA.

Let’s take another example where P = “AB” and T = “ABA”, and one sub-pattern is P[2...2] = “B”, then we can find these matches “ABA”, “ABA” and “ABA”

Now, given the texts in the secret document, the pattern and the indices of the optional sub-pattern, you will have to determine how many times the pattern has occurred in the document.

Input

The first line contains the text of the document. The text will contain at most 10510^5 alphanumeric characters. The second line contains the pattern PP, which will also contain at most 10510^5 alphanumeric characters. The third line will contain a non-negative integer DD, the number of optional sub-patterns in pattern DD. The next DD lines each will contain a pair of integers xx and yy (1x,yP1 \le x, y \le |P|), the starting and ending indices of one optional sub-pattern. Here, P|P| indicates the length of the pattern PP.

The number of different sub-patterns possible to create using optional sub-patterns and mandatory sub-patterns will be less than or equal to 1000.

Output

Output a single line, printing the number of times the pattern has occurred in the text. Output the result modulo 1000000009. Two match will be different if any of the optional or mandatory sub-strings occurs at a different place of the text (see the first sample for further explanation).

Empty string won’t be counted as a match.

Samples

InputOutput
a
aaaaa
5
1 1
2 2
3 3
4 4
5 5
5
InputOutput
ABCXYADGHA
ABCADA
2
2 3
4 5
7

Submit

Login to submit.

Statistics

50% Solution Ratio
nfssdqEarliest, Dec '15
nusuBotFastest, 0.0s
nfssdqLightest, 11 MB
user.1267Shortest, 3144B
Toph uses cookies. By continuing you agree to our Cookie Policy.