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
#include<iostream>
#include<algorithm>

using namespace std;

#define MOD 1000000007
#define M 108
typedef long long Int;

int a, b, c, d, e;
Int dp[108][21600];
Int dp1[108][21600];
Int dp2[108][21600];
int main(){
  cin >> a >> b >> c >> d >> e;
  b -= a;
  e -= a*d;
  dp[0][0] = 1;
  dp1[0][0] = 1;
  dp2[0][0] = 1;
  for(int i = 0;i <= d;i++){
    for(int j = 0;j < 21500;j++){
      if(i == 0 && j == 0)continue;
      dp[i%M][j] = 0;    
      int l = max(0, i - j);
      int r = min(c, i);
	  if(l <= r){
	      if(i-l>=0 && j - (i-l) >= 0)dp[i%M][j] += dp1[(i-l)%M][j-(i-l)];
	      if(i-(r+1) >= 0 && j-(i-(r+1)) >= 0)dp[i%M][j] -= dp1[(i-(r+1))%M][j-(i-(r+1))];
	  }
/*      for(int k = l;k <= r;k++){
	dp[i][j] += dp[i-k][j-(i-k)];
	} */
      l = 1;
      r = min(c, i);
      r = min(r, j / (b+1));
      if(l <= r){
	      if(i-l >= 0 && j-(b+1)*l >= 0)dp[i%M][j] -= dp2[(i-l)%M][j-(b+1)*l];
	      if(i-(r+1) >= 0 && j-(b+1)*(r+1) >= 0)dp[i%M][j] += dp2[(i-(r+1))%M][j-(b+1)*(r+1)];
	  }
/*      for(int k = l;k <= r;k++){
	dp[i][j] -= dp[i-k][j-(b+1)*k];
	}*/
      dp[i%M][j] %= MOD;
      if(dp[i%M][j] < 0)dp[i%M][j] += MOD;
      dp1[i%M][j] = dp2[i%M][j] = dp[i%M][j];
      if(i)(dp1[i%M][j] += dp1[(i-1)%M][j+1])%=MOD;
      if(i && j-(b+1)>=0)(dp2[i%M][j] += dp2[(i-1)%M][j-(b+1)])%=MOD;
    }
  }
  cout << dp[d%M][e] << endl;
  return 0;
}
