All submissions for this problem are available.
Aniket is obsessed with strings. One day he wondered how many strings of length N exist whose every K length substring is a palindrome. Of course, such strings depend on the number of letters of the language of strings(like English language has 26 letters). He is interested in finding the sum of number of strings for the languages having L,L+1.... R letters. Since Aniket has to go Mumbai this weekend hence he is busy. Solve the problem for him. Since the answer can be very large, print it modulo 1000000007(10^9+7)
Note: A palindromic string is a string that is read same both forward and backwards. Eg. abba is a palindrome but abbd is not.
The first line of the input contains 3 integers N K Q denoting the length of strings, length of palindromic substrings and number of queries. Then Q lines follow with each line having two integers L and R for each query.
Print Q lines each containing the sum of number of strings of length N whose every K length substring is palindrome for languages having L, L+1, L+2 ... R letters.
- 1 ≤ N ≤ 5000
- 1 ≤ K ≤ 5000
- 1 ≤ Q ≤ 10^5
- 1 ≤ L ≤ R≤ 10^3
Input: 5 4 3 1 3 2 4 4 5 Output: 6 9 9
For query 1 the example strings are aaaaa (for language having 1 letter), aaaaa, bbbbb (for language having 2 letters), aaaaa, bbbbb, ccccc (for language having 3 letters). Hence the sum is 6.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP 4.3.2, CPP 6.3, CPP14, PYTH, PYTH 3.5|
Fetching successful submissions
If you are still having problems, see a sample solution here.