ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural SU contest. Petrozavodsk training camp. Winter 2009

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. Killer Words

Time limit: 1.0 second
Memory limit: 64 MB
Federal Security Agency is extremely interested in the loyalty of its special agents. To provide this loyalty they developed a killer words technology: if an agent doesn't execute orders anymore, it is enough to pronounce a special word to activate a bomb in the brain of the agent and eliminate him.
The bomb should not be activated accidentally, so the killer word should be quite special: it should contain only first m letters of english alphabet and should be a k-repetition, that is, it should be possible to represent it as a concatenation of k equal words. Moreover, to exclude the possibility of killing unnessecary agents, no proper substring of a killer word can be a k-repetition. Your task is to calculate the number of words which can be used as killer words and consist of at most n letters.

Input

The first line contains space-separated integers m, k, n (1 ≤ m ≤ 18; 2 ≤ k ≤ 5; 1 ≤ n ≤ 22).

Output

Output the required number of killer words.

Sample

inputoutput
3 2 4
9
Problem Author: Alex Samsonov
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, February 2009
To submit the solution for this problem go to the Problem set: 1694. Killer Words