Problem description

Wuj Janusz opowiadał wczoraj Jasiowi o swojej wycieczce do bardzo egzotycznego kraju. Tamtejszy król ogłosił Bardzo Ważne Słowo s i zakazał jego dzielenia. Dotyczy to nie tylko przenoszenia jego części do nastepnej linii, ale również przecinania nożyczkami itp. Znajomy wuja Janusza, który tam mieszka, robił akurat remont w domu i musiał przeciąć belkę sufitową. Niestety na całej długości belki jest napis, który może zawierać Bardzo Ważne Słowo.

Jasio teraz zastanawia się, na ile sposobów można było podzielić tę belkę na dowolnie wiele części. Niestety, kiedy tata dowiedział się o rozterkach syna, zadał mu K tak trudnych pytań, że Jasia rozbolała głowa i oprosił cię o pomoc. Każde z tych pytań wygląda następująco: Na ile sposobów można było podzielić tę belkę na dokładnie c części?

Ponieważ odpowiedzi na powyższe pytania mogą być bardzo dużymi liczbami, wypisz je modulo 10⁹ + 7.

Wejście

W pierwszym wejściu znajdują się trzy liczby naturalne S, N, K. Oznaczające kolejno długości Bardzo Ważnego Słowa i napisu na belce oraz liczbę pytań taty Jasia.

Następne dwa wiersze zawierą odpowiednio Bardzo Ważne Słowo i napis na belce składające się z małych liter alfabetu angielskiego.

Kolejne K wierszy opisuje pytania taty Jasia, każdy z nich zawiera jedną liczbę całkowitą c.

Wyjście

W pierwszym wierszu wyjścia należy wypisać jedną liczbę całkowitą – liczbę podziałów belki na dowolnie wiele części. Następne K wierszy powinno zawierać odpowiedzi na pytania taty Jasia, w kolejności, w której pojawiły się na wejściu.

Ograniczenia

1 ≤ S, N ≤ 500000, 0 ≤ K ≤ 100000, 1 ≤ c ≤ N.

Przykład

5 17 7
abbab
cabbabbabcdeabbab
1
2
3
4
5
6
7

32
1
5
10
10
5
1
0

Podzadania