移动金币
描述
一个 \(1\times n\) 的棋盘上最初摆放有 \(m\) 枚金币。
其中每一枚金币占据了一个独立的格子,任意一个格子内最多只有一枚金币。
Alice和Bob将要进行如下的一场游戏。二人轮流操作,且Alice先行。
当轮到一个玩家的时候,他可以选择一枚金币,并将其向左移动任意多格,且至少移动一格。
金币不能被移出棋盘,也不能越过其它金币。
如果轮到一个玩家的时候他已经无法做出任何有效操作了(显然这个时候\(m\)枚金币恰好落在最左侧的\(m\)个格子中),则被判定为输家。已经知道Alice和Bob都是极致聪明的人,他们在任何局面下总能做出最优的操作。那么有多少初始状态能保证Alice必胜呢?
格式
输入格式
输入仅有一行并包含两个正整数,依次为\(n\)和\(m\),如题目所述。
输出格式
输出一个整数,表示有多少初始状态可以保证Alice作为先手方能先手必胜。由于答案可能很大,请输出关于\(10^9+9\)取模后的值。
样例1
样例输入1
10 3
样例输出1
100
样例2
样例输入2
199 43
样例输出2
981535230
样例3
样例输入3
99999 47
样例输出3
39178973
限制
数据规模
子任务\(1\):(\(50\)分)\(1\le n\le 250\)且\(1\le m\le 50\)。
子任务\(2\):(\(50\)分)\(1\le n\le 150000\)且\(1\le m\le 50\)。
时限
1s
内存限制
默认
信息
- ID
- 2055
- 难度
- 4
- 分类
- (无)
- 标签
- (无)
- 递交数
- 130
- 已通过
- 54
- 通过率
- 42%
- 被复制
- 3
- 上传者