Во времена Ясона и Аргонавтов, было хорошо известно, что сирены используют свои песни, чтобы заманивать моряков к себе на погибель. Но немногие знали, что каждый раз сирены, когда зовут моряков по имени, те становятся слабее и более уязвимыми.

Для целей этой задачи, и песни сирен, и имена моряков будем представлять строками, состоящими из строчных английских букв. Чем больше раз имя моряка появляется как непрерывная подстрока в песне, тем моряк в большей опасности.

Ясон обнаружил, что сирены могут петь одну из $$$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$$$.