背景

stong9070穿越到了公元66666年，在66666年的社会，有一个恶霸ARM,stong9070想替天行道，为民除害与ARM对战，战力不敌ARM，被ARM封印在了Minecraft服务器中，当了一个队长。stong9070是有雄心壮志的，他想要带领他的战队统治整个Minecraft服务器 。

题目

为了达成这个目标，他决心带领他的战队练习箭术（在大型战役中，远程攻击能力是很重要的），而stong9070则要以身作则，他在几十公外放上了一个标靶，并将队员们叫来观摩他射箭，stong9070的箭术很好，所以他每次射箭都会射中标靶，且射中标靶每一处的概率均等。

标靶上只有红白两种颜色，但面积并不相同，所以stong9070会有$p$/$q$的概率射中红色处，1-($p$/$q$)的概率射中白色处。而且，当射中红色处的箭与射中白色处的箭的数量的差的绝对值超过1，stong9070就不会继续射箭了

现在stong9070想知道，他射出且仅射出了$n$支箭的概率是多少。

设这个概率表示为$x/q^n$，请输出的值$x$ $mod$ $10^9+7$的值

输入格式

输入一行三个正整数$p,q,n$意义如题中所述

输出格式

输出一行，一个数表示stong9070射出且仅射出了$n$支箭的概率$x/q^n$的分子$x$取模$10^9+7$

样例

1 2 4

4

数据范围

• 对于10%的数据$n\leq10$
• 对于40%的数据$n\leq40$
• 另有10%的数据$n$为奇数
• 对于100%的数据 $0\leq p \leq q \leq 10^9,2\leq n \leq10^6$