You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

棋子现在在 $(0,0)$ 点，它想 恰好 用 $K$ 步移动到 $(x,y)$ 点。它每一步可以移动到上下左右 相邻 的点，但不能移动到 $x$ 轴下面，也不能移动到 $y$ 轴左边。请你求出方案数。

• 注：“上上下下右右上上左左下下”是一个合法的移动。

Format

Input

$K,x,y$

Output

输出方案数，答案对 $1e9+7$ 取模。

Samples

4 1 1

16

Limitation

$0≤K,x,y≤10^{6}$