Prerak Mall
Palindromaniac
1 Answer(s)      5 years and a month ago
Posted in : Java Beginners

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

March 4, 2012 at 7:10 AM

```# 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 ;
}
```