Problems
Killer Words
Killer Words
Federal Security Agency is extremely interested in the loyalty of its special agents. To provide this loyalty they developed a \textit{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 \textbf{m} letters of english alphabet and should be a \textbf{k}-\textit{repetition}, that is, it should be possible to represent it as a concatenation of \textbf{k} equal words. Moreover, to exclude the possibility of killing unnessecary agents, no proper substring of a killer word can be a \textbf{k}-repetition. Your task is to calculate the number of words which can be used as killer words and consist of at most \textbf{n} letters.
\InputFile
The first line contains space-separated integers \textbf{m}, \textbf{k}, \textbf{n} (\textbf{1} ≤ \textbf{m} ≤ \textbf{18}; \textbf{2} ≤ \textbf{k} ≤ \textbf{5}; \textbf{1} ≤ \textbf{n} ≤ \textbf{22}).
\OutputFile
Output the required number of killer words.
Input example #1
3 2 4
Output example #1
9