You've got string s, consisting of characters from an alphabet of size Q.
some of the strings are good, the rest are bad.
A string is good if every substring of length R, in the original string of length R is palindrome. The task is to determine the number of such unique good strings. output answer in modulo (10^9+7).

Input:
three integers P,Q,R
6 3 2
output:
3

Explaination:
P=6, alphabet: {x,y,z} , R=2. We have Q=3 and we want every substring of length 2 to be palindrome.
Then following strings of length 6 are allowed: xxxxxx, yyyyyy and zzzzzz.