#1040. 环

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: tony102

题目描述

求满足下列条件的本质不同的环的数目:

这个环由 个黑色珠子和 个白色珠子构成 这个环上不会出现连续的 个黑色珠子 我们认为两个环是相同的,当且仅当一个环通过旋转之后能够得到另外一个环。答案可能会非常大,所以你只需要输出答案对于 取模之后的结果。

输入格式

输入只有一行三个整数 n m k,其含义见题目描述。

输出格式

输出一行一个整数,表示答案

样例

见附加文件

数据范围与提示

  • 对于 的数据,保证
  • 对于 的数据,保证
  • 对于另外 的数据,保证
  • 对于另外 的数据,保证
  • 对于另外 的数据,保证
  • 对于 的数据,保证