# lss1.dp - Dynamic Programming

Version: v2

2000ms / 262144 KB
Difficulty:1.0x

# Statement

Doragon is a Aqua Dragon girl. It is said that she has 300IQ.

XGN asked her to try some OI problems. So she did. After solving A+B Problem. She decided to see some DP problems.

It's known that $F(1,1)=1$ and $F(0,x)=F(x,0)=0$ for any X. It's also known that $F(i,j)=aF(i-1,j)+bF(i,j-1)$ What an easy DP

# Input

One line four integer: a,b,N,M

Proceed to the EOF.

# Output

Print one integer, the answer module 1e9+7

# Example

[Input]
1 1 2 2
1 1 3 3
1 2 2 2
[Output]
2
6
4
[Explain]
The F matrix when a=1 b=1 is
1 1 1
1 2 3
1 3 6
The F matrix when a=1 b=2 is
1 2
1 4


Subtask 1(10%):$1\leq A,B,N,M,T \leq 100$
Subtask 2(40%):$1\leq A,B,N,M,T \leq 1000$
Subtask 3(50%):$1\leq A,B,N,M,T \leq 10^5$