Poem Titles#210
Recently, the inhabitants of a distant planet passed an amendment to the "Poem Titles" section of the "Copyright Protection" law in a referendum.
Previously, the law required poem titles to be sequences consisting only of 0s and 1s.Now, each new poem title must not only consist of 0s and 1s, but must also not contain as a substring the title of any already published work.
After the referendum, they published a list of all existing poem titles on their website. With each new poem, they plan to update this list.
Upon learning of this legislative change, a local poet decided to name all his masterpieces using sequences of length .Visiting the website, he saw that the list already contained previously published works.He became curious how many more poems he could write without violating the new law. Trying to count, the poet realized the task was very difficult. Help the poet determine how many possible poem titles he can use.As the answer may be very large, output the result modulo .
The first line contains three numbers: , (K \leq 1000), and (P \leq 2 \cdot 10^9).The following lines each contain a title, which is a sequence of 0s and 1s. Each title has length at most .Note: Before the law was amended, some poem titles might have been identical, but they were not removed from the list.
Output the number of sequences of length that the poet can use for his poem titles, modulo , without violating the new law and without changing his rule about the length of titles.
Example 1