Palindromaniac

Palindromaniac

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

View Answers

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









Related Tutorials/Questions & Answers:
Palindromaniac

Ads