时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
看到隔壁养了一堆纳米兔子，竭泽动起了歪心思，养起了一堆纳米猫猫。
纳米猫猫就不一样了，他们根本没有那种世俗的欲望（和竭泽一样），不需要配偶，自力更生，自给自足，自己就能繁殖。纳米猫猫在每个月能生下x只纳米猫猫，新生的纳米猫猫在下个月也能生出孩子，而且每一只都能生出x个孩子，但是每次生完孩子的猫猫就会跑出去，不理竭泽了。
竭泽愣住了。
竭泽在第一个月买了一只纳米猫猫，想知道第n个月，竭泽身边能有几只猫猫没有跑掉 ？
由于答案可能特别大，答案对数字mod取模。
纳米猫猫就不一样了，他们根本没有那种世俗的欲望（和竭泽一样），不需要配偶，自力更生，自给自足，自己就能繁殖。纳米猫猫在每个月能生下x只纳米猫猫，新生的纳米猫猫在下个月也能生出孩子，而且每一只都能生出x个孩子，但是每次生完孩子的猫猫就会跑出去，不理竭泽了。
竭泽愣住了。
竭泽在第一个月买了一只纳米猫猫，想知道第n个月，竭泽身边能有几只猫猫没有跑掉 ？
由于答案可能特别大，答案对数字mod取模。
输入描述:
一行三个数字，
输出描述:
输出答案