К Коле на день рождения придут n друзей.
По этому случаю он заготовил n бутылок различных напитков, а каждый из друзей принесет свой стакан.
Коля знает размеры стаканов каждого друга, однако, может случится так, что содержимое конкретной бутылки может не поместиться полностью в конкретный стакан, если объем бутылки больше объема стакана. При этом Коля не хочет, чтобы после угощения что-то осталось, поэтому будет разливать напитки только так, чтобы они полностью поместились в стаканы. Напиток полностью помещается в стакан, если объем, содержащей его бутылки, не превосходит объем стакана.
Коля хочет своеобразно оценить сколько способов есть разлить напитки по стаканам друзей так, чтобы все напитки полностью поместились в стаканы. Так как число способов может быть довольно большим, Коля хочет знать его по модулю 1 000 000 007. Помогите Коле посчитать это число.
Входные данные
В первое строке дано число t - число тестовых наборов (1≤t≤100).
Каждый тестовый набор задается тремя строками. В первой из них дано число n
i - число стаканов и бутылок напитков в i-ом наборе (1≤n
i≤10
5).
Во второй строке даны n
i чисел b
i,j - объемы стаканов в i-м наборе (1≤a
i,j,b
i,j≤100).
В третьей строке заданы n
i чисел a
i,j - объемы бутылок в i-м наборе.
Гарантируется, что сумма n
i по всем тестовым наборам не превосходит 3⋅10
5.
Выходные данные
Для каждого тестового набора выведите одно число - число способов разлить напитки по стаканам друзей так, чтобы все напитки полностью поместились в стаканы, взятое по модулю 1 000 000 007.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
3
3
1 1 1
1 2 1
5
1 2 3 4 5
1 2 3 4 5
3
2 2 2
2 1 2 |
0
1
6 |
В первом тестовом наборе второй напиток не помещается ни в один стакан, поэтому ответ будет ноль. Во втором тестовом наборе, существует лишь один способ разлить напитки. В третьем наборе любой напиток можно налить в любой стакан. |