题目描述

一个极地站包含 $N$ 个传感器和两个研究人员居住舱。传感器编号为 $0,1,\ldots,N-1$，并按这个顺序分布在同一个圆周上。两个居住舱编号为 $N$ 和 $N+1$。

暴风雪之前一共有 $2N+1$ 条道路：

• 传感器沿圆周相邻连接，共 $N$ 条道路，其中还包括 $0$ 与 $N-1$ 之间的道路；
• 每个传感器恰好与一个居住舱相连，共 $N$ 条道路；
• 两个居住舱之间还有一条道路。

其中，编号 $lo,lo+1,\ldots,hi$ 的传感器与居住舱 $N$ 相连，其余传感器与居住舱 $N+1$ 相连。

暴风雪覆盖了所有道路。研究人员希望清理一些原有道路，使得所有传感器和两个居住舱重新连通。为了尽量少劳动，他们只愿意清理最少数量的道路。显然，若最终全部 $N+2$ 个点连通，最少恰好需要清理 $N+1$ 条道路。

求有多少种不同的道路集合满足要求。两种方案不同，当且仅当被清理的道路集合不同。

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

输入格式

一行三个整数：

N lo hi

输出格式

输出一个整数，表示合法方案数量对 $10^9+7$ 取模后的结果。

数据范围

• $3\le N\le10^9$；
• $0\le lo\le hi\le N-1$。

样例 1

3 0 2

16

样例 2

3 1 1

24

样例 3

10 1 4

28325