Avoid Prefix Palindromes
Practice
1 (1 votes)
Dynamic programming
Algorithms
String
Medium
Introduction to dynamic programming 1
Problem
72% Success 181 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

A special palindrome is a palindrome of size \(N \) which contains at most \(K \) distinct characters such that any prefix of size between \(2\) and \(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 and K = 3, possible special palindromes are aba, aca, bab, bcb, cac and cbc. So the answer will be 6.

Input format

A single line comprising two integers \(N\) and \(K\)

Output format

Print the answer to the modulo \(10^9 + 9 \).

Input Constraints

\(1 \le N \le 10^5\)

\(1 \le K \le 10^5 \)

 

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:50
40 votes
Tags:
ApprovedData StructuresFenwick TreeHardOpenSegment TreesTrees
Points:30
Tags:
HiringOpenRecruitHiringOpenRecruitHiringSortingImplementationAdvanced SortingAdvanced sortingAlgorithmsGreedy algorithmEasy
Points:20
Tags:
Easy