题目描述

Andra 被中国文化，尤其是长城深深吸引，于是决定用红色和黄色的构件建造一堵属于自己的墙。墙的高度为 $N$，宽度为 $M$。

她拥有无限多个构件。每个构件的宽度恒为 $1$，高度可以是任意正整数。

构件有两种颜色：

• 红色构件的高度必须是奇数：$1,3,5,\ldots$；
• 黄色构件的高度必须是偶数：$2,4,6,\ldots$。

构件不能旋转，只能竖直放置。

由于黄色在中国文化中具有重要含义，Andra 希望整堵墙中所有黄色构件的高度总和恰好等于 $K$。她想知道，在满足这个条件的情况下，有多少种不同的建墙方案。

两个方案被认为相同，当且仅当每个位置上的构件类型完全相同。注意，同样颜色也可能因为分段方式不同而形成不同方案。例如，高度为 $4$、宽度为 $1$ 且全为黄色的墙有两种建法：一个高度为 $4$ 的黄色构件，或两个高度为 $2$ 的黄色构件。

任务

给定 $N,M,K$，求满足条件的不同建墙方案数。

答案对 $10^9+7$ 取模。

输入格式

输入一行，包含三个整数 $N,M,K$。

输出格式

输出一行一个整数，表示满足条件的建墙方案数，答案对 $10^9+7$ 取模。

数据范围

• $1\le N,M\le 5000$
• $0\le K\le N$

子任务

样例 1

输入

5 1 2

输出

6

共有 $6$ 种高度为 $5$、宽度为 $1$，且黄色构件高度总和为 $2$ 的建墙方案。

样例 2

输入

2 2 2

输出

2

共有 $2$ 种建墙方案。