ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Autumn school contest 2008

About     Problems     Submit solution     Judge status     Standings
Contest is over

H. Godzilla Strikes Back!

Time limit: 1.0 second
Memory limit: 64 MB
As you all know, a DNA is a string over an alphabet {'A', 'C', 'G', 'T'}. In 2567, scientists from the Cytology and Genetics Research Institute decided to create an extremely powerful giant pangolin called Bugzilla. It is known that the height and the power of the pangolin is completely determined by its DNA. The process of creating Bugzilla's DNA took m days. The scientists had a bank of numbered DNAs, which initially contained 2 DNAs of some mutant pangolins. These DNAs were numbered 1 and 2. On day k, the scientists chose DNAs number i and j from the bank (i can be equal to j), concatenated them to form a new DNA and added it to the bank, assigning number k + 2 to it. Finally, after m days the desired DNA of a giant pangolin was formed (it had a number m + 2 in the bank). Somehow the newspapers found out about these experiments, and the citizens began to panic. What to expect from a new, more powerful monster, if its prototype, Godzilla, was bad enough to destroy the city completely? To answer this question you should count the number of occurences of Godzilla's DNA in Bugzilla's one.


The first line contains Godzilla's DNA from a museum of the Cytology and Genetics Research Institute. Its length doesn't exceed 100. The next two lines contain two DNAs of the mutant pangolins, which were initially in the bank. The length of each of these DNAs is at most 10. The forth line contains an integer m (1 ≤ m ≤ 100) — the day Bugzilla's DNA was created on. Then follow m lines. k-th line contains a pair of space-separated integers (from 1 to k + 1) — the numbers of DNAs from the bank which were concatenated by scientists on k-th day.


Output the number of occurences of Godzilla's DNA in Bugzilla's one modulo 109 + 7.


1 2
2 1
3 1
5 4
1 1
3 3


In the first sample, the scientists consecutively obtained the following DNAs: AG, GA, AGA, AGAGA. AGA occurs twice in AGAGA.
In the second sample, the following DNAs were obtained: CTCT, CTCTCTCT. A doesn't occur in CTCTCTCT.
Problem Author: Ivan Burmistrov
Problem Source: USU Junior Contest, October 2008
To submit the solution for this problem go to the Problem set: 1646. Godzilla Strikes Back!