让二追三
题号:NC261390
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

正如大家所见,守望先锋目前无国服,国人的联赛队伍无有效训练对手,只有极其一般的报酬,也没有未来的期冀。在这应该是最后一年的OWL守望先锋联赛季后赛里,杭州闪电队被暴雪定为八号种子。(季后赛采用BO5的机制,即先取得三分的队伍赢得对战)
第一场,杭州闪电队和之前赛程里展现无敌统治力的西部一号种子亚特兰大君临对战。第一局,0:1惜败。第二局,0:2。第三局,1:2。第四局,2:2。第五局,3:2!让二追三,成功拿下君临!
第二场,杭闪和拥有四个总冠军选手的超级豪门波士顿崛起对战。第一局,漓江塔,崛起的女王冲脸阵容暂时难以招架,0:1;第二局,国王大道,杭州的进攻势如破竹,可惜防守时放的路太远了,最后一波团输在了大招数,0:2;第三局,苏拉瓦萨,在mmonk的神之睡针加持下,杭闪避免了多次致命伤害,反击开始!1:2;第四局,新皇后街,guxue的铁拳拳拳到肉,拉扯、输出、配合,多次在团队不利的情况下创造对方的缺口,拿下!2:2;第五局,66号公路。多么戏剧化,上场让二追三的第五局也是66号公路。杭闪防守方,崛起队的车离B点仅剩0.01m,guxue成功赶到卡车,并且leave先手带走双辅,赢下这波团战,后面团战的leave更是超神四杀,最终车卡在了B点!杭闪进攻方,开局不利,A点打到加时,shy超频成功突破。进入B段,shy激素超频三杀,杭闪成功到点!杭州闪电队再次让二追三!成功进入四强! 

(以上题目背景可无视)
你也想像杭闪打出让二追三的操作,于是打开守望先锋,进行了n场比赛。我们定义“让二追三”为,连续五场比赛为“输输赢赢赢”。你的每场比赛获胜的概率是p(p=a/b),你想知道在n场比赛里你能打出的“让二追三”在模1e9+7下的期望次数。

简单来说,有一个长度为n01串,其中每一位是1的概率是p(p=a/b),是0的概率是1-p。问这个01串中 00111 这个子段在模1e9+7下的期望个数。

提示,x/y在模1e9+7下等于x*y',其中y'y在模1e9+7下的乘法逆元。

输入描述:

第一行一个正整数T,表示有T组数据。

接下来的T行,每行三个正整数a,b,n。(a/b表示一场比赛赢的概率,n表示比赛的场数。)

0<a<b\leq 10000
1\leq T\leq 10^5
1\leq n\leq 10^5

输出描述:

输出T行,每行输出一个整数,表示在模1e9+7下的00111的期望个数。
示例1

输入

复制
1
4 5 5

输出

复制
711360005
示例2

输入

复制
1
206 530 23805

输出

复制
430700962