CF1466G Song of the Sirens

Whoso in ignorance draws near to them and hears the Sirens' voice, he nevermore returns.Homer, Odyssey In the times of Jason and the Argonauts, it was well known that sirens use the sound of their songs to lure sailors into their demise. Yet only a few knew that every time sirens call a sailor by his name, his will weakens, making him more vulnerable. For the purpose of this problem, both siren songs and names of the sailors will be represented as strings of lowercase English letters. The more times the sailor's name occurs as a contiguous substring of the song, the greater danger he is in. Jason found out that sirens can sing one of the $ n+1 $ songs, which have the following structure: let $ s_i $ ( $ 0 \leq i \leq n $ ) be the $ i $ -th song and $ t $ be a string of length $ n $ , then for every $ i < n $ : $ s_{i+1} = s_i t_i s_i $ . In other words $ i+1 $ -st song is the concatenation of $ i $ -th song, $ i $ -th letter ( $ 0 $ -indexed) of $ t $ and the $ i $ -th song. Fortunately, he also knows $ s_0 $ and $ t $ . Jason wonders how many times a sailor's name is mentioned in a particular song. Answer $ q $ queries: given the sailor's name ( $ w $ ) and the index of a song ( $ i $ ) output the number of occurrences of $ w $ in $ s_i $ as a substring. As this number can be quite large, output its remainder modulo $ 10^9+7 $ .

N/A

N/A

In the first example songs of the sirens are as follows: - Song $ 0 $ : aa - Song $ 1 $ : aabaa - Song $ 2 $ : aabaacaabaa - Song $ 3 $ : aabaacaabaadaabaacaabaa