В 2567 году учёные из НИИ Цитологии и Генетики решили создать Багзиллу — огромного ящера, обладающего чудовищной силой. Как известно, рост и силу ящера целиком и полностью определяет его ДНК — специальная строка, состоящая из символов 'A', 'C', 'G', 'T'. В первые 2 дня учёные получили большое количество образцов ДНК двух ящеров-мутантов, которые впоследствии собирались использовать для получения ДНК Багзиллы. Каждый день они учились склеивать два ранее полученных образца ДНК, тем самым получая новый образец в количестве, достаточном для проведения дальнейших экспериментов. Наконец, через m дней они достигли желаемого результата — была получена ДНК ящера необычайного роста и силы. Информация об этом просочилась в прессу, и вот тут-то в городе началась паника. Уж если легендарный Годзилла в своё время камня на камне не оставил от города, то чего же ждать от его копии, ещё более чудовищной? Чтобы выяснить это, необходимо как можно быстрее посчитать, сколько раз ДНК Годзиллы встречается как подстрока в ДНК Багзиллы.

В первой строке записана непустая строка, состоящая только из символов 'A', 'C', 'G', 'T', — образец ДНК Годзиллы, хранящийся в музее НИИ Цитологии и Генетики. Длина этой строки не превосходит 100 символов. В двух следующих строках записаны образцы ДНК ящеров, с которых начался процесс клонирования. Эти образцы представляют собой непустые строки длиной не более 10, также состоящие из символов 'A', 'C', 'G', 'T'. В четвёртой строке записано целое число m (1 ≤ m ≤ 100) — количество полученных учёными образцов ДНК (без учёта первых двух). Далее следуют m строк, k-я из них содержит пару целых чисел в пределах от 1 до k + 1 — номера образцов ДНК, которые учёные научились склеивать в (k + 2)-й день экспериментов. Новая ДНК получается приписыванием второй ДНК в конец первой.

Найдите число вхождений ДНК Годзиллы в ДНК Багзиллы и выведите его по модулю 10⁹ + 7.

В первом примере учёными были получены последовательно следующие образцы ДНК: AG, GA, AGA, AGAGA. ДНК AGAGA дважды содержит ДНК AGA как подстроку.

Во втором примере были получены последовательно следующие образцы ДНК: CTCT, CTCTCTCT. ДНК CTCTCTCT не содержит ДНК A.