Gunga changes his computer's password once a week, and he has a list of $$$n+1$$$ different passwords. In week 1, he has the first password in his list as his password. At the beginning of every week, he changes his password. He chooses $$$1$$$ out of the other $$$n$$$ passwords randomly to be his new password. However, there's $$$\frac{1}{m}$$$ chance that he forgets changing it each week. More formally, there is $$$\frac{1}{m}$$$ chance of not changing the password and $$$\frac{m-1}{m}$$$ chance of changing it to a different one chosen by random.
Unfortunately, at the end of the $$$T$$$-th week, careless Gunga forgot his password again! If the maximum possible number of attempts for Gunga is $$$k$$$ and he is trying all the possible passwords in the list's order, what is the probability that he can open his computer?
In other words, what is the probability that he uses one of the first $$$k$$$ passwords on his list in the $$$T$$$-th week? Assume that the answer is a reduced fraction of the form $$$\frac{x}{y}$$$ ($$$\gcd(x, y)=1$$$), output integer $$$z$$$ such that $$$zy\equiv x \pmod{10^9+7}$$$. In other words, output $$$x y^{-1} \pmod{10^9+7}$$$.
A single line containing 4 integers $$$n,m,k,T$$$ $$$(1\le n,m,k\le 10^9,1\le T\le 10^5)$$$.
Assume that the answer is a reduced fraction $$$\frac{x}{y}$$$, output $$$xy^{-1}\pmod{10^9+7}$$$.
3 2 3 4
92592594
100 37 53 4568
490435543
In the first example, let $$$P_1,P_2,P_3,P_4$$$ denote the probability of using the $$$i$$$-th password.
On the first week, Gunga is using the 1st password.
On the second week, $$$P_1=\frac12,P_2=P_3=P_4=\frac16$$$.
On the third week, $$$P_1=\frac13,P_2=P_3=P_4=\frac29$$$.
On the fourth week, $$$P_1=\frac{5}{18},P_2=P_3=P_4=\frac{13}{54}$$$.
The answer is
$$$$$$\frac{5}{18}+\frac{13}{54}+\frac{13}{54}=\frac{41}{54}$$$$$$ Thus $$$x=41, y=54$$$.
We should output $$$41\cdot 54^{-1} \pmod{10^9+7} = 92592594$$$
If you are not familiar with getting $$$x^{-1}$$$ under modular arithmetic, Yifan has prepared a code for you in c++! (For people with different coding languages, try using the code as a reference and come up with your own!)
https://pastebin.com/SuD839YA
