9999004 - 集合

【题目描述】 小 P 有 n 个字符串,所有字符串的每一个位置都是一个介于 0 ∼ k − 1 的数 字。 现在小 P 有一个字符串的集合 S,S 是由 n 个字符串的全部前缀组成。 但是粗心的小 P 弄丢了这 n 个字符串,他只记得这些字符串的长度都是 p, 现在他想知道,在所有可能的情况中,|S|(即集合 S 的大小) 的最大值是多少。

输入

【输入格式】 文件 set.in 中读入数据。 共一行三个整数 n, k, p。

输出

【输出格式】 输出到文件 set.out 中。 共一行一个整数表示答案。

样例

输入

9 2 8

输出

59

输入

100 2 100

输出

9526
时间限制 1 秒
内存限制 512 MB
统计
上一题 下一题