India’s Best Job Seekers and Training Platform Forums Algorithm Solutions Discussion A special palindrome is a palindrome of size N which contains …

  • A special palindrome is a palindrome of size N which contains …

  • Akash 

    Administrator
    at

    A special palindrome is a palindrome of size N which contains atmost K distinct characters such that any prefix between the size 2 to N-1 is not a palindrome.

    You need to count the number of special palindromes

    For example, abba is a special palindrome with N=4 and K=2 and ababa is not a special palindrome because aba is a palindrome and its a prefix of ababa.

    If N=3, K=3, possible special palindromes are aba, aca, bab, bcb, cac and cbc. So answer will be 6.

    Input format

    Two integers N and K

    Output format

    Answer modulo 10^9+9

    Constraints

    1<=N,K<=10^9

    Sample TC

    3 3

    Output

    6

Log in to reply.

Original Post
0 of 0 posts June 2018
Now
KodNest Training New Batch is starting on 21st September 2020. Attend one week free demo classes.Register Now

New Report

Close