Prerak Mall
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 ;
}
- Difference between equals() and == ?
- Assignment operator in java
- Hibernate Video Tutorial
- Conditional operator in java
- jQuery Tutorial For Beginners
- Show pdf's in web browser by using jsp?
- Google says Start Searching India
- Most Effective SEO Tools
- Assigning value to anchor <a></a> tag using custom tag
- java code using while loop
