Prashanthwagle360
BAN USER
- 2
1of 3 votes
AnswersA 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.
- Prashanthwagle360 in India
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| Report Duplicate | Flag | PURGE
HackerEarth Problem Setter Algorithm
- 40
Repbettylfoster, University dean at Littler's
Hi , I am Betty from the USA , working as Dien in Littler's University for the last three years. Previously ...
- 0
Rep
- 0
RepTaylahMacge, Consultant at Accenture
Assigned to manage the requirements of foreign clients specifically those from the Chinese, Arabic, and French-speaking markets.I am passionate ...
- 40
Repmarkhlee8, Research Scientist at Bank of America
I am a cooking Instructor in New York USA, I Have a degree from the prestigious Culinary Arts Institute of ...
- 0
RepHello friends my name Neha Nanda from India Chandigarh city. Doing work in SEO line in Softsys company.
- 0
Repmarktrejjo, Data Engineer at Accolite software
I’m Mark.I believe life is too short to be serious all the time, so if you cannot laugh ...
- 30
RepTinaaJohn, Cloud Support Associate at AMD
Hi,Everyone.I am an art teacher at Woodson Institute.Foster and encourage critical thinking and analysis about art and ...
- 30
Repjuanajcox4, Python Developer at Axiom Sources
I have 2 years of experience in designing and implementing computer algorithms or models for creating, displaying, and processing various ...
- 0
RepJenniferSRoe, Android test engineer at Accolite software
I am Jennifer from Dublin. I am Photographer, I have experienced in all different kinds of photography -Strong aesthetic sense ...
- 30
Repkevinlmoses, Animator at Accenture
I am Experienced Building Manager who is an expert in public and industrial safety with a preventative mindset against fire ...
- 10
RepI am an energetic sales professional with a track record of consistently increasing sales revenue in a competitive market. Contract ...