#6357. game

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

题目描述

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

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

输入格式

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

输出格式

求编号为 1 的人最后存活的概率对 10^9+7 取模后的值。

样例

样例输入

2 1

样例输出

333333336

样例解释

\frac{1}{4} + \frac{1}{16} + \frac{1}{64} + \frac{1}{256} + \cdots = \frac{1}{3}

数据范围与提示

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