Problem F: Sum of Numbers

Problem

a以上b以下の整数が書かれたカードがそれぞれc枚ずつあります。 これらc(b-a+1)枚のカードの中からd枚のカードを選択したとき、それらのカードに書かれている整数の合計がeになる場合の数を1,000,000,007で割った余りを求めてください。

Input

入力は以下の形式で与えられる。

a b c d e

1行目に、5つの整数a b c d eが空白区切りで与えられる。

Constraints

入力は以下の制約を満たす。

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

Output

場合の数を1,000,000,007で割った余りを出力せよ。

Sample Input1

2 5 3 3 11

Sample Output1

3

{2,2,2,3,3,3,4,4,4,5,5,5}の中から3枚選び合計が11になるのは、 {2,4,5},{3,3,5},{3,4,4}の３通りである。

Sample Input2

1 2 3 4 100

Sample Output2

0

{1,1,1,2,2,2}の中から4枚選び合計が100になるのは0通りである。

---