#P8359. [ioi2018国家队集训]宝藏

    ID: 8446 传统题 5000ms 512MiB 尝试: 3 已通过: 2 难度: 9 上传者: 标签>数论CF2600数学概率论递归模运算状压DP搜索

[ioi2018国家队集训]宝藏

宝藏(treasure)

题目描述

有 nn 个洞穴,宝藏位置在开始时从全部洞穴中等概率选定,之后保持不动。 每天可以派出 kk 个机器人检测洞穴。机器人只有在检测宝藏所在洞穴时, 才以概率 p0p_0 找到宝藏;各次检测是否成功相互独立,且 0<p0≤10<p_0\le1。

你可以根据此前的未成功检测选择每天的搜索安排。求采用最优策略时, 首次找到宝藏的期望天数。第1天开始检测;当天至少一个机器人成功即视为找到。

概率 p0=u/vp_0=u/v 是有理数,且 vv 与 M=109+7M=10^9+7 互质。 输入中的字段 pp 是 uv−1 mod Muv^{-1}\bmod M 的标准代表元。 数据保证最优期望是有限有理数,且其最简分母与 MM 互质。 若期望为最简分数 x/yx/y,输出 xy−1 mod Mxy^{-1}\bmod M。

输入格式

第一行一个整数 TT。 接下来 TT 行,每行三个整数 n,k,pn,k,p。

输出格式

每组数据输出一行一个整数,表示期望天数的模值。

样例

6
1 1 500000004
2 1 500000004
3 2 500000004
1 1 333333336
2 1 333333336
3 2 333333336
2
500000007
777777786
3
500000009
866666677

数据范围

1≤T≤10001\le T\le1000,1≤k≤n≤5000000001\le k\le n\le500000000,1≤p<M1\le p<M。 概率及期望还须满足题目描述中的可逆性保证。

参考附件

原题资料(本页约定为准)