#6357. game

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

题目描述

nnn 个人逆时针排成一个环,从编号为 111 的人开始逆时针从 111kkk 报数,报到 kkk 的人有 12\frac{1}{2}21 的概率出局。无论其出局与否,下一个人报 111

求编号为 111 的人最后存活的概率。

输入格式

只有一行,两个整数 n,kn, kn,k

输出格式

求编号为 111 的人最后存活的概率对 109+710^9+7109+7 取模后的值。

样例

样例输入

2 1

样例输出

333333336

样例解释

14+116+164+1256+⋯=13\frac{1}{4} + \frac{1}{16} + \frac{1}{64} + \frac{1}{256} + \cdots = \frac{1}{3}41+161+641+2561+=31

数据范围与提示

对于 100%100\%100% 的数据,n≤2000,k≤109n \le 2000,k \le 10^9n2000,k109