题目描述

NCPC 评审团决定在编程比赛前先进行一项体育活动，好让参赛者热血沸腾。随机抽签后，他们选中了棒球。现在问题变成：如何铺出一个合适的棒球场。

评审团有一块大小为 $a imes b$ 米的矩形土地，以及 $N$ 块大小为 $1 imes 1$ 米的正方形草皮。所有草皮都必须放在这块矩形土地内，并且边必须与土地边界平行。矩形土地的西南角被选为击球点。

一种草皮摆放方案构成合法棒球场，当且仅当满足以下两个条件：

1. 对于任意一块草皮，它的南侧和西侧必须要么紧贴土地边界，要么直接紧贴另一块草皮。这个条件用于保证球沿直线运动时不会先离开场地再重新进入场地。
2. 所有“北侧和东侧都没有相邻草皮”的草皮，到击球点的曼哈顿距离必须相同。这个条件用于防止击球手偏好某些方向。

请计算有多少种摆放全部 $N$ 块草皮的方法，使得它们构成合法棒球场。

输入格式

第一行包含一个正整数 $N$，表示草皮数量。

第二行包含两个正整数 $a,b$，表示矩形土地的尺寸。

输出格式

输出一个整数，表示合法摆放方案数。由于答案可能很大，请输出答案对 $10^9+7$ 取模后的结果。

数据范围

• $1 \le N \le 10^4$
• $1 \le a,b \le 10^4$

样例

输入 #1

15
3 8

输出 #1

3

输入 #2

15
3 5

输出 #2

1

输入 #3

15
3 4

输出 #3

0