#3114. 「SDOI2019」移动金币

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Ycrpro

题目描述

一个 1\times n 的棋盘上最初摆放有 m 枚金币。其中每一枚金币占据了一个独立的格子,任意一个格子内最多只有一枚金币。

Alice 和 Bob 将要进行如下的一场游戏。二人轮流操作,且 Alice 先行。当轮到一个玩家的时候,他可以选择一枚金币,并将其向左移动任意多格,且至少移动一格。金币不能被移出棋盘,也不能越过其它金币。

如果轮到一个玩家的时候他已经无法做出任何有效操作了(显然这个时候 m 枚金币恰好落在最左侧的 m 个格子中),则被判定为输家。已经知道 Alice 和 Bob 都是极致聪明的人,他们在任何局面下总能做出最优的操作。那么有多少初始状态能保证 Alice 必胜呢?

输入格式

输入仅有一行并包含两个正整数,依次为 n m ,如题目所述。

输出格式

输出一个整数,表示有多少初始状态可以保证 Alice 作为先手方能先手必胜。由于答案可能很大,请输出关于 10^9+9 取模后的值。

样例

样例输入 1

10 3

样例输出 1

100

样例输入 2

199 43

样例输出 2

981535230

样例输入 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