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]$ and $P[a...b]$ are included in our pattern, then either $y < a$ or $b < 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, **A**BCXY**A**DGHA, **ABC**XY**A**DGHA, **A**BCXYADGH**A**, **ABC**XYADGH**A**, **A**BCXY**AD**GH**A**, **ABC**XY**AD**GH**A** and ABCXY**A**DGH**A**.

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 “**A**BA”, “AB**A**” and “**AB**A”

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.

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

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 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.

Input | Output |
---|---|

a aaaaa 5 1 1 2 2 3 3 4 4 5 5 | 5 |

Input | Output |
---|---|

ABCXYADGHA ABCADA 2 2 3 4 5 | 7 |

Toph uses cookies. By continuing you agree to our Cookie Policy.