Palindromic Substrings

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.
Input
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.
Output
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.
Constraints
 1 ≤ N ≤ 5000
 1 ≤ K ≤ 5000
 1 ≤ Q ≤ 10^5
 1 ≤ L ≤ R≤ 10^3
Example
Input: 5 4 3 1 3 2 4 4 5 Output: 6 9 9
Explanation
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.
Author:  mrityunjaypm 
Tags  mrityunjaypm 
Date Added:  26102015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, PYTH, PYTH 3.5 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 