# D. Time to go back

time limit per test：1 second

memory limit per test：256 megabytes

input：standard input

output：standard output

You have been out of Syria for a long time, and you recently decided to come back. You remember that you have M friends there and since you are a generous man/woman you want to buy a gift for each of them, so you went to a gift store that have N gifts, each of them has a price.

You have a lot of money so you don't have a problem with the sum of gifts' prices that you'll buy, but you have K close friends among your M friends you want their gifts to be expensive so the price of each of them is at least D.

Now you are wondering, in how many different ways can you choose the gifts?

Input

The input will start with a single integer T, the number of test cases. Each test case consists of two lines.

the first line will have four integers N, M, K, D (0  ≤  N, M  ≤  200, 0  ≤  K  ≤  50, 0  ≤  D  ≤  500).

The second line will have N positive integer number, the price of each gift.

The gift price is  ≤  500.

Output

Print one line for each test case, the number of different ways to choose the gifts (there will be always one way at least to choose the gifts).

As the number of ways can be too large, print it modulo 1000000007.

Examples

Input

```2
5 3 2 100
150 30 100 70 10
10 5 3 50
100 50 150 10 25 40 55 300 5 10```

Output

```3
126```

......

``` 1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
5 {
6     ll x=0,f=1;
7     char ch=getchar();
8     while(ch<'0'||ch>'9')
9     {
10         if(ch=='-')
11             f=-1;
12         ch=getchar();
13     }
14     while(ch>='0'&&ch<='9')
15     {
16         x=x*10+ch-'0';
17         ch=getchar();
18     }
19     return x*f;
20 }
21 inline void write(ll x)
22 {
23     if(x<0)
24     {
25         putchar('-');
26         x=-x;
27     }
28     if(x>9)
29         write(x/10);
30     putchar(x%10+'0');
31 }
32 ll vis[210][210];
33 ll val[210];
34 const ll mod=1000000007;
35 bool cmp(ll a,ll b)
36 {
37     return a>b;
38 }
39 int main()
40 {
41     for(int i=0;i<210;i++)
42     {
43         vis[i][0]=1;
44         for(int j=1;j<=i;j++)
45         {
46             vis[i][j]=((vis[i-1][j-1]%mod)+(vis[i-1][j]%mod))%mod;
47         }
48     }
50     while(t--)
51     {
52         ll ans=0,pos=0;
57         for(ll i=0;i<n;i++)
59         sort(val,val+n,cmp);
60         for(ll i=0;i<n;i++)
61         {
62             if(val[i]>=d)
63                 ans++;
64             else break;
65         }
66         if(n-ans==0)
67             pos=vis[ans][m];
68         else if(ans<k||n<m)
69             pos=0;
70         else
71         {
72             for(ll i=k;i<=ans;i++)
73             {
74                 if(m-i<0)
75                     break;
76                 pos=(pos+(vis[ans][i]*vis[n-ans][m-i])%mod)%mod;
77             }
78         }
79         write(pos);
80         printf("\n");
81     }
82     return 0;
83 }```

0 条评论

## 相关文章

2885

### HUDOJ-----1394Minimum Inversion Number

Minimum Inversion Number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit:...

3666

### HDU 5877 2016大连网络赛 Weak Pair(树状数组，线段树，动态开点，启发式合并，可持久化线段树)

Weak Pair Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144...

37810

### BZOJ 2456: mode(新生必做的水题)

2456: mode Time Limit: 1 Sec  Memory Limit: 1 MB Submit: 4868  Solved: 2039 Des...

2696

### HDUOJ 2672---god is a girl 《斐波那契数》

god is a girl Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/3276...

2796

### Code forces 719A Vitya in the Countryside

A. Vitya in the Countryside time limit per test:1 second memory limit per test:2...

3466

### Educational Codeforces Round 44 (Rated for Div. 2)A. Chess Placing

You are given a chessboard of size 1 × n. It is guaranteed that n is even. The c...

1172

### Java_数据交换_JAXB_用法入门

JAXB（Java Architecture for XML Binding) 是一个业界的标准，是一项可以根据XML Schema产生Java类的技术。该过程...

1043

1175