All submissions for this problem are available.
Jesse Pinkman is caught by the cops when he is trying to sell some meth.
But the cops will release him if he can help them with this problem.
The cops gave Jesse a string S and an integer N, along with another integer K. Jesse has to find the number of strings X such that X is of exactly N length and contains S as a substring atleast K times.
Note: that while counting the number of times S occurs in X, we have to also count overlapping occurrences. For example, if S is "aba" and X is "ababa" then we say that S occurred twice in X (overlapping).
Both the string can contain only lowercase english alphabets from 'a' through 'z'.
- The first line of the input contains two space separated integers K and N as described above.
- Next line contains the string S.
- Output a single integer, the required answer modulo 10^9+7.
- 1 ≤ N ≤ 10^9
- 1 ≤ K*(Length of String S) ≤ 100
Input 1: 1 2 aa Output: 1 There is only 1 string of length 2 "aa" in which the string "aa" occurs as a substring at least 1 time.
Input 2: 5 100 aabab Output: 893894668
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY|
Fetching successful submissions