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 10⁹ + 7.

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.