Кто по незнанию приближается к ним и слышит голос сирен, тот больше не возвращается.Гомер, Одиссея
Во времена Ясона и Аргонавтов, было хорошо известно, что сирены используют свои песни, чтобы заманивать моряков к себе на погибель. Но немногие знали, что каждый раз сирены, когда зовут моряков по имени, те становятся слабее и более уязвимыми.
Для целей этой задачи, и песни сирен, и имена моряков будем представлять строками, состоящими из строчных английских букв. Чем больше раз имя моряка появляется как непрерывная подстрока в песне, тем моряк в большей опасности.
Ясон обнаружил, что сирены могут петь одну из \(n+1\) песен, которые имеют следующую структуру: пусть \(s_i\) (\(0 \leq i \leq n\)) будет \(i\)-й песней, а \(t\) — некоторой строкой длины \(n\), тогда для всех \(i < n\): \(s_{i+1} = s_i t_i s_i\). другими словами, \(i+1\)-я песня это конкатенация \(i\)-й песни, \(i\)-й буквы (в \(0\) индексации) строки \(t\), и \(i\)-й песни.
К счастью, он также знает \(s_0\) и \(t\). Ясон интересуется, сколько раз имя моряка встречается в конкретной песне. Ответьте на \(q\) вопросов: дано имя моряка (\(w\)) и номер песни (\(i\)), выведите количество вхождений \(w\) в \(s_i\) как подстроки. Так как это число может быть довольно большим, выведите его по модулю \(10^9+7\).