Easy Recurrence#6090
Sign in

Easy Recurrence

8 seconds
64 megabytes
Hard

You are given four positive integers , , , and , which define the following recurrence:

x_n = \begin{cases} 1, & \text{if } n \leq 0 \\ c \cdot x_{n-a} + d \cdot x_{n-b}, & \text{if } n > 0 \end{cases}

Given , compute x_n \bmod 1000000007.

Input

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

Output

Output x_n \bmod 1000000007.

Examples

Example 1

Loading
Loading