Problem

There are c cards each with an integer between a and b. When d cards are selected from these c (b-a + 1) cards, the remainder when the sum of the integers written on those cards is e is divided by 1,000,000,007 is calculated. please.

Constraints

The input satisfies the following constraints.

• 1 ≤ a ≤ 1000
• a ≤ b ≤ 1000
• 1 ≤ c ≤ 100
• 1 ≤ d ≤ 1000
• c ≤ d ≤ c (b-a + 1)
• 1 ≤ e ≤ 20000

Input

The input is given in the following format.

a b c d e

On the first line, five integers a b c d e are given, separated by blanks.

Output

Output the remainder of dividing the number of cases by 1,000,000,007.

Examples

Input

2 5 3 3 11

Output

3

Input

1 2 3 4 100

Output

0

见题面

见题面