该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

小王是一名喜欢数学管道工。

他有 $W(\le10^9)$ 根高度为 $H(\le100)$ 的长水管，另有无限的无区别的长度为 1 的连接水管（只能用于连接长水管，不能互相连接）。

一开始，他把 $W$ 根长水管竖立固定在墙上，每两根水管之间的距离为 1 。

他可以用连接水管连接相邻的长水管。由于技术限制，同一个位置最多只能连接一根连接水管，并且连接水管的两端的高度距离地面必须是正整数，连接水管仅能连接相邻的长水管。

小王还养了一只猫。每次这只猫都会爬到第一根长水管的顶部。然后按照如下规则爬行：

如果某个位置有连接水管，那么就顺着连接水管爬行到长水管。否则，就沿着长水管向下爬行。

问有多少种连接方式，可以使得小猫能够用这种方式移动到第 $K(\le W)$ 根水管。

不要求使用的连接水管数量最少。

Format

Input

一行三个正整数 $H$ 、 $W$ 和 $K$ 。

Output

输出方案数，对 $1\ 000\ 000\ 007$ 取模。

Samples

3 4 4

4

Limitation

1s, 1024KiB for each test case.