约瑟夫环存活概率问题

题目描述

n 个人逆时针排成一个环，从编号为 1 的人开始逆时针从 1 至 k 报数。报到 k 的人有 $\frac{1}{2}$ 的概率出局，无论其是否出局，下一个人都将从 1 开始继续报数。

求编号为 1 的人最后存活的概率，结果需对 $10^9+7$ 取模。

输入格式

一行两个整数 n, k，分别表示人数和报数阈值。

输出格式

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

样例输入

2 1

样例输出

333333336

样例说明

当 n=2、k=1 时，存活概率为无穷级数之和： $\frac{1}{4} + \frac{1}{16} + \frac{1}{64} + \frac{1}{256} + \cdots = \frac{1}{3}$。 由于 $\frac{1}{3}$ 对 $10^9+7$ 取模的结果为 333333336（即 $3^{-1} \mod 10^9+7$），故输出该值。

数据范围与提示

对于 100% 的数据，满足 $2 \leq n \leq 2000$，$1 \leq k \leq 10^9$。