"Easy Recurrence"

You are given four positive integers a, b, c, and d, which define the following recurrence:

x_{n }= 1 for n ≤ 0,

x_{n }= cx_n_{-a }+ dx_n_{-b} for n > 0.

For a given n find x_n mod 1000000007.

Input

The only line of the input contains five integers a, b, c, d, and n (1 ≤ a < b ≤ 2000, 1 ≤ c, d ≤ 100, 1 ≤ n ≤ 10^9).

Output

Output x_n mod 1000000007.

Examples