Gravity Machine Synchronization

A gravity machine consists of a smooth circular track with \(2n\) small holes numbered \(1,2,\dots,2n\) in counter‐clockwise order. The minor arc between every two adjacent holes has an angle of \(\frac{\pi}{n}\). Moreover, every hole is connected by a tunnel to the hole whose radial line forms an angle \(\pi\) with it. For example, when \(n=2\) hole \(1\) is connected to hole \(3\).

A ball is placed at hole \(1\) of the machine and starts moving along the circle with a uniform speed in the counter–clockwise direction. In the absence of teleportation the ball moves from one hole to the next exactly in one unit of time. However, due to the strange construction of the laboratory (the internal gravitational device is simply magical!), every time the ball passes through a hole it has a probability \(p\) to instantaneously teleport (without spending time) to the hole on the opposite side and then continue moving with a uniform speed in the counter–clockwise direction. (In other words, at every time step the ball located at hole \(i\) will go to hole \(i'\) where

[ \text{next hole } = \begin{cases} (i \bmod 2n) +1, & \text{with probability } 1-p,\[1mm] ((i+n-1) \bmod (2n)) +1, & \text{with probability } p. \end{cases} ]

Note that if a teleportation happens the ball does not stop at the intermediate hole (only the hole where the ball comes to rest is counted). Also, teleportation may occur at the very beginning of the motion.

The experimentalist TLX now has two identical gravity machines. A ball is started simultaneously in each machine from hole \(1\). Then TLX uniformly and randomly picks a pair \((i,j)\) with \(1 \le i \le 2n\) and \(0 \le j \le t\) (with \(i,j \in \mathbb{Z}\)). Your task is to compute the probability that at time \(j\) both machines have a ball at rest at hole \(i\> (note that if a ball passes a hole only because it teleports then it is not considered to be resting there).

All probabilities (and the final answer) are computed under modulo \(10^9+7\>.

inputFormat

The input consists of a single line containing three integers \(n\), \(t\), and \(p\) (where \(0 \le p \le 10^9+6\)). Here, \(n\) represents half the number of holes (so that there are \(2n\) in total), \(t\) represents the maximum time, and \(p\) is the probability (given in modulo arithmetic) that a ball teleports when passing a hole.

outputFormat

Output a single integer: the required probability (in modulo \(10^9+7\)) that, if a pair \((i,j)\) is chosen uniformly at random among \(1 \le i \le 2n\) and \(0 \le j \le t\), both machines have a ball resting at hole \(i\) at time \(j\>.

sample

2 1 0

250000002