题目描述

一个只由1∼m数码组成的n位数, 如果任意两个相邻数之差的绝对值都不超过d,则称这个数是一个"d好数".

给出n,m,d,输出n位"d好数"的个数. d的值只可能取1,2,3.

输入格式

1行,3个正整数n,m,d

输出格式

输出n位"d好数"的个数

输入样例 #1

5 3 1

输出样例 #1

99

输入样例 #2

1 1 1

输出样例 #2

1

输入样例 #3

10 9 3

输出样例 #3

78747531

数据范围与约定

1 ≤ n ≤ 10，1 ≤ m ≤ 9，1 ≤ d ≤ 3。