#P1357. 花园
花园
题目描述
小 L 有一座环形花园,沿花园的顺时针方向,他把各个花圃编号为 。花园 和 是相邻的。
他的环形花园每天都会换一个新花样,但他的花园都不外乎一个规则:任意相邻 个花圃中都只有不超过 个 C 形的花圃,其余花圃均为 P 形的花圃。
例如,若 , , ,则
CCPCPPPPCC
是一种不符合规则的花圃。CCPPPPCPCP
是一种符合规则的花圃。
请帮小 L 求出符合规则的花园种数对 取模的结果。
输入格式
只有一行三个整数,分别表示 。
输出格式
输出一行一个整数表示答案。
10 5 3
458
6 2 1
18
提示
数据规模与约定
- 对于 的数据,保证 。
- 对于 的数据,保证 。
- 对于 的数据,保证 ;
- 对于 的数据,保证 ,,。