Sacred sequence codes
HardOnline Assessment
Count the keypad codes that contain a house's sacred sequence exactly once.
A temple door has a keypad with q keys, labelled with the first q lowercase letters ("a", "b", ...). A code is a string of exactly n key presses. The temple's sacred sequence is the string word. A code is blessed if word appears in it exactly once as a run of consecutive key presses.
Occurrences are allowed to overlap, and each starting position counts as its own occurrence: in the code "aaa", the sequence "aa" occurs twice (starting at index 0 and at index 1). A code in which the sequence occurs twice or more, or not at all, is not blessed.
Input: n, the code length, q, the number of keys, and word, the sacred sequence (made only of the first q letters).
Output: the number of blessed codes, modulo 1,000,000,007. If n is smaller than the length of word, no code can contain it, so return 0.
There are q^n codes, far too many to look at one by one, so the count has to be built up cleverly.
Example 1
- Input:
- [3,2,"ab"]
- Output:
- 4
- Explanation
- With keys a and b, the strings of length 3 containing
abexactly once areaab,aba,abbandbab. The other four strings (aaa,baa,bba,bbb) contain noab.
Example 2
- Input:
- [4,2,"aa"]
- Output:
- 5
- Explanation
- Occurrences may overlap, and each one counts. The valid strings are
aabb,aaba,baab,abaaandbbaa. A string likeaaabis rejected becauseaaoccurs twice (at positions 0 and 1), andaaaacontains it three times.
Example 3
- Input:
- [5,2,"aba"]
- Output:
- 10
- Explanation
- Eleven strings of length 5 contain
abaat least once, butababacontains it twice (positions 0 and 2, sharing the middlea), so it is rejected. The answer is 10:aaaba,aabaa,aabab,abaaa,abaab,ababb,baaba,babaa,babab,bbaba.
Constraints
1 <= n <= 2,0002 <= q <= 261 <= word.length <= 12, and every character ofwordis one of the firstqlowercase letters