题目描述

Fox Jiro 和 Eel Saburo 是好朋友。一天，Jiro 给 Saburo 出了下面这个问题。

有一个高为 $H$、宽为 $W$ 的矩形网格。每个格子中都填有一个 $0$ 到 $S$ 之间（包含端点）的非负整数，并且左上角格子的数值固定为 $0$。

从左上角格子出发，每一步只能移动到正下方或正右方的相邻格子，直到到达右下角。设一条路径经过的所有格子（包括终点）中的整数之和为 $K$。

Saburo 不会使用动态规划求最优路径，于是采用下面的贪心策略：

• 如果当前位于最右一列，则只能向下移动；
• 如果当前位于最下一行，则只能向右移动；
• 否则，比较正下方与正右方两个相邻格子的数值，移动到数值较大的格子；如果两者相等，则移动到右边的格子。

如果按照上述贪心算法得到的路径上所有格子的数值之和恰好等于 $p$，则称这个网格为 $p$-贪心网格。

给定 $H,W,S$，求满足条件的 $S$-贪心网格 的数量。由于答案可能很大，只需输出答案对 $10007$ 取模后的结果。

注意：这里的 $S$ 同时表示每个格子允许填写的最大值，以及要求贪心路径上的数值之和。

输入格式

一行三个整数 $H,W,S$，分别表示网格的高度、宽度以及格子中允许出现的最大整数。

输出格式

输出一个整数，表示不同的 $S$-贪心网格数量对 $10007$ 取模后的结果。

样例 #1

输入

2 2 1

输出

4

样例 #2

输入

2 2 2

输出

9

样例 #3

输入

2 2 0

输出

1

样例 #4

输入

47 58 100

输出

1301

数据范围

对于所有测试数据：

• $1\le H\le 2500$；
• $1\le W\le 2500$；
• $0\le S\le 100$。