Hiking Trails

Time limit1sMemory limit512 MB

Summary

Count ordered alternating sequences of distinct east and west trails, bridged by x, whose total length falls in [C, D].

Level: Hard8 of 10
Topics: Dynamic programming, Bit manipulation, Combinatorics, Math
Solved: No attempts yet

Problem

Albert enjoys hiking.

Near Albert's house there is a large mountain to the east and another to the west, and each has hiking trails of various lengths.

The east mountain has n hiking trails (for convenience, let their lengths be A[1], ..., A[n]) and the west mountain has m hiking trails (for convenience, let their lengths be B[1], ..., B[m]).

All n trails of the east mountain start at the same place (the east mountain entrance) and end at the same place, and likewise all m trails of the west mountain start at the same place (the west mountain entrance) and end at the same place.

The entrances of the east and west mountains are connected by a separate "east-west bridge" of length x. In the figure below, the east mountain entrance is drawn as a square and the west mountain entrance as a circle, and the east-west bridge connecting the two entrances has length x = 10. The two east mountain trails have lengths 40 and 45, and the two west mountain trails both have length 42.

Albert wants to plan a hike whose total length is at least C and at most D, following the rules below. (A hike plan says which trails are used and in what order.)

The same trail is used at most once.
Trails of the same mountain are not used consecutively (that is, trails of the east mountain and the west mountain are used alternately).
Moving from one mountain to the other always uses the east-west bridge of length x, and there is no other path (the east-west bridge may be used multiple times).
The east-west bridge cannot be at the very beginning or the very end of the hike, and the east-west bridge cannot be used consecutively. Therefore, whenever the east-west bridge is used, a trail of the east mountain or the west mountain must be used before and after it.

For example, in the figure above, n = m = 2, x = 10, A = [40, 45], and B = [42, 42]. Let C = 1 and D = 100. There are 12 hike plans with length between 1 and 100 that satisfy all the rules above.

There are 4 hike plans with total length between 40 and 45 (using any one of the four trails).
There are 8 hike plans with total length between 92 and 97 (choosing one trail from each mountain, then deciding the order in which to hike them).

Given n, m, x, C, D, and A, B as input, help Albert find the number of ways to plan a hike.

Input

The first line of input gives the number of test cases T.

Each test case is given over three lines.

The first line gives n, m, x, C, D, separated by spaces.

The second line gives n integers, separated by spaces, representing the lengths of the east hiking trails.

The third line gives m integers, separated by spaces, representing the lengths of the west hiking trails.

Output

For each test case, print the answer on its own line. The answer can be very large, so print it modulo $10^9+7$ .

Constraints

$1 \le T \le 5$
$1 \le n, m \le 18$
$1 \le x \le 10^8$
$1 \le C \le D \le 10^9$
$1 \le$ length of each hiking trail $\le 10^8$

Examples2

Example 1

Input

3
3 5 100 245 245
10 20 30
1 2 3 4 5
5 5 1 39 39
1 2 3 4 5
5 4 3 2 1
5 5 1 1 3
1 1 1 1 1
1 1 1 1 1

Expected output

2
28800
60

Example 2

Input

3
2 2 10 1 100
45 40
42 42
16 16 10 100 100
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
18 18 100000000 900000000 900000000
100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000
100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000

Expected output

12
0
2996352