文理学院程序设计在线练习


unkindled ash

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 8   Accepted Submission(s): 3
Problem Description

"The fire will eventually extinguish."
as an unkindled ash, your mission is to continue the Age of Fire, link the fire.
Finally you got N cinders' souls to restrike the first fire, but some of the fire seedbed is too fragile.
You now have N souls altogether, meanwhile the number of fire seedbed is also N.For each fire seedbed, you need at least A_i energy to restrike it, and each souls' energy is represented as a positive integer B_i.
notice that each fire seedbed only and must put in one cinders' soul, even if the energe of souls can not restrike it.
you need to restrike *exactly* K fire seedbed to accomplish mission as a Ash. Now you want to find out that How many ways you can restrike the fire.
(you can assume that put the souls one by one into the different fire seedbed as an independent solution).

Input

First line contains a positive integer T, represent the number of testcases.
For each testcase, first line contains two positive interger n and k, represent the number of fire seedbed, and the at number of fire you need to restrike exactly.
next lines contains n integers A_i, represent the energe which each fire seedbed needs.
next lines contains n integers B_i, represent the energe of each cinders' souls.
0 <= T <= 20;
0 <= K <= N <= 2000;
0 <= A_i, B_i <= 1000000000;
0 <= ΣN <= 4000;

Output

For each testcase, output the number of solution mod by 10^9+7.

Sample Input
2
4 4
1 1 1 1
1 1 1 1
4 2
2 2 1 1 
1 1 2 2 
Sample Output
24
4
Source

2019绍兴联赛