#A0586. 再次抓住牛

再次抓住牛

题目描述

33DAI 进入了游戏世界,变成了一个二维小人,站在了一个长度为 nn 的尺子上,尺子上有 n+1n+1 个刻度 0n0\sim n

33DAI 在刻度 aa 的位置,牛在刻度 bb 的位置。每次 33DAI 可以往左或者或者往右跳,每次可以跳一个刻度或者两个刻度,但不能跳到一个跳过了的位置,一但跳到了牛的位置 33DAI 会立刻停止。

请你算算 33DAI 有多少种方案跳到牛的位置。

比如上面的例子中,33DAI 有如下这些方法:

  • 1 -> 2 -> 3
  • 1 -> 2 -> 4 -> 3
  • 1 -> 0 -> 2 -> 3
  • 1 -> 0 -> 2 -> 4 -> 3
  • 1 -> 3

输入格式

三个数 n,a,bn,a,b

输出格式

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

4 1 3
5
4 3 4
4

样例 2 解释

有下面这些方案

  • 3 -> 4
  • 3 -> 1 -> 2 -> 4
  • 3 -> 2 -> 4
  • 3 -> 1 -> 0 -> 2 -> 4
4 0 1
4

样例 3 解释

  • 0 -> 1
  • 0 -> 2 -> 4 -> 3 -> 1
  • 0 -> 2 -> 1
  • 0 -> 2 -> 3 -> 1
1000000 1000000 500000
267385954
1000000 400000 500000
727245392
1000000 0 1000000
746580045

数据规模与约定

对于 100%100\% 的数据,1n1061 \le n \le 10^60a,bn0\le a,b\le naba\neq b

  • 子任务 1(10 分):保证 n10n\le 10a=0a=0b=nb=n
  • 子任务 2(20 分):保证 a=0a=0b=nb=n
  • 子任务 3(30 分):保证 n20n\le 20
  • 子任务 4(40 分):没有特殊限制。