4B 两种操作

4B 两种操作

两种操作

时间限制:1s
空间限制:64MB

题目描述

给定一个正整数\(X\),我们希望可以通过一系列操作,将其变成0。

操作分为两种:
1.将当前数乘以2。
2.将当前数减去1。

要求,在变换过程中,数字始终不能为负数(即\(X\)为0时可以乘以2,但不能减去1)

现在已知:
1.操作1进行了\(N\)次,操作2进行了\(M\)次。
2.最后一步是\(X\)由1进行操作2变为0。

求满足上述条件的操作有多少种可能?

输入格式

第一行包含三个整数\(X\),\(N\)和\(M\)。

输出格式

输出一个整数表示答案。由于答案可能很大,输出模\(1000000007\)的结果。

输入样例

2 5 10

输出样例

14

样例解释

14种可能的操作如下
212121121222222
212112212212222
211222112212222
122212112212222
211221222112222
122211222112222
122122212112222
212112122222122
211221221222122
122211221222122
122122211222122
211212222212122
122122122212122
121222221212122

数据范围

对于 50% 的数据,\(1 \leq N,M \leq 10\)。
对于 100% 的数据,\(1 \leq N,M \leq 100\),\(1 \leq X \leq M\)。

信息

ID
1356
难度
8
分类
(无)
标签
(无)
递交数
101
已通过
12
通过率
12%
上传者