Ever wondered about strings full of palindromes? The strange folks in the magical world of mamamam speak in such strings.
You might have noticed that every sub-string of length three in "mamamam" is a palindrome.
You have been given a task by the half-lion half-goat king of mamamam who wants to devise a language for mamamam.
You are to find the number of strings with length N such that every sub-string of length K of such a string is a palindrome. Furthermore these strings are restricted to an alphabet containing only M symbols.
Since this number can be very large, output it modulo 1000000007, the king's favourite prime number. Input A single line containing the integers N, M and K Output A single line containing the number required.
Sample Inputs
Input: 3 2 2
Output: 2
Input: 4 3 2
Output: 3
# include<stdio.h> # include<stdlib.h> # include<string.h> long long int modular_pow(long long int base,long long int exponent, long long int modulus) ; int main() { long long int i,j,m,n,k,z,ans; scanf("%lld%lld%lld",&n,&m,&k); z=k-(k/2)*2; if(z==0){ ans = modular_pow(m,k/2,1000000007); } else { ans = modular_pow(m,(k+1)/2,1000000007); } printf("%lld\n",ans); return 0 ; } long long int modular_pow(long long int base,long long int exponent, long long int modulus) { long long int result = 1 ; while (exponent > 0) { if ((exponent & 1) == 1) { result = (result * base) - ((result * base)/modulus)*modulus ;} exponent = exponent >> 1 ; base = (base * base) - ((base * base)/modulus)*modulus ; } return result ; }
Ads