问题 6256 --3.再次抓住牛

6256: 3.再次抓住牛

题目描述

33DAI 进入了游戏世界,变成了一个二维小人,站在了一个长度为 $n$ 的尺子上,尺子上有 $n+1$ 个刻度 $0\sim n$。 ![](/upload/image/20240911/233836_40285.png) 33DAI 在刻度 $a$ 的位置,牛在刻度 $b$ 的位置。每次 33DAI 可以往左或者或者往右跳,每次可以跳一个刻度或者两个刻度,但不能跳到一个跳过了的位置,一但跳到了牛的位置 33DAI 会立刻停止。 请你算算 33DAI 有多少种方案跳到牛的位置。 比如上面的例子中,33DAI 有如下这些方法: - `1 -> 2 -> 3` - `1 -> 2 -> 4 -> 3` - `1 -> 0 -> 2 -> 3` - `1 -> 0 -> 2 -> 4 -> 3` - `1 -> 3`

输入

三个数 $n,a,b$。

输出

输出 33DAI 有多少种方案跳到牛的位置。次数可能会很多,请输出对 $10^9+7$ 取模后的结果。

样例输入输出

输入#1 复制
4 1 3
输出#1 复制
5
输入#2 复制
4 3 4
输出#2 复制
4
输入#3 复制
4 0 1
输出#3 复制
4
输入#4 复制
1000000 1000000 500000
输出#4 复制
267385954
输入#5 复制
1000000 400000 500000
输出#5 复制
727245392
输入#6 复制
1000000 0 1000000
输出#6 复制
746580045

提示

【样例 2 解释】 ![](/upload/image/20240911/233937_74323.png) 有下面这些方案 - `3 -> 4` - `3 -> 1 -> 2 -> 4` - `3 -> 2 -> 4` - `3 -> 1 -> 0 -> 2 -> 4` 【样例 3 解释】 - `0 -> 1` - `0 -> 2 -> 4 -> 3 -> 1` - `0 -> 2 -> 1` - `0 -> 2 -> 3 -> 1` 对于 $100\%$ 的数据,$1 \le n \le 10^6$,$0\le a,b\le n$,$a\neq b$。 - 子任务 1(10 分):保证 $n\le 10$,$a=0$,$b=n$。 - 子任务 2(20 分):保证 $a=0$ 且 $b=n$。 - 子任务 3(30 分):保证 $n\le 20$。 - 子任务 4(40 分):没有特殊限制。
序号 标题 作者 发表时间 费用 订购数 操作