등산로

Albert는 등산을 즐겨한다.

Albert의 집 근처에는 동쪽과 서쪽에 각각 큰 산이 있고, 다양한 길이의 등산로가 마련되어있다.

동쪽 산에는 n개의 등산로가 있고 (편의상 이들의 길이를 A[1], ..., A[n]이라 하자) 서쪽 산에는 m개의 등산로가 있다 (편의상 이들의 길이를 B[1], ..., B[m]이라 하자).

동쪽 산의 n개의 등산로는 모두 같은 곳 (동쪽 산 출입구) 에서 시작하여 같은 곳에서 끝나고, 마찬가지로 서쪽 산의 m개의 등산로도 모두 같은 곳 (서쪽 산 출입구)에서 시작하여 같은 곳에서 끝난다.

동쪽 산과 서쪽 산의 입구는 길이가 x인 별도의 "동서 다리"를 통해 연결되어있다. 아래 그림에서 동쪽 산의 출입구는 정사각형으로, 서쪽 산의 출입구는 원으로 표시되어있고 두 출입구를 잇는 동서 다리의 길이는 x = 10 이다. 동쪽 산의 두 등산로의 길이는 각각 40과 45이고 서쪽 산의 두 등산로의 길이는 42로 동일하다.

Albert는 아래와 같은 규칙에 따라 총 길이가 C이상 D이하가 되도록 등산 계획을 세우고 싶다: (등산 계획은 어떤 등산로를 어떤 순서로 이용하는지 나타낸다)

1. 같은 등산로는 최대 한 번만 이용한다.
2. 같은 산의 등산로는 연속으로 이용하지 않는다 (즉, 동쪽 산과 서쪽 산의 등산로를 번갈아 이용한다).
3. 어떤 산에서 다른 산으로 이동할 때에는 반드시 길이가 x인 동서 다리를 이용하며, 다른 길은 없다 (동서 다리는 여러 번 이용해도 된다).
4. 동서 다리는 등산 계획의 맨 처음이나 맨 끝에 올 수 없고, 동서 다리는 연속으로 이용할 수 없다. 따라서 동서 다리를 이용할 경우 반드시 전/후에 동쪽 산 혹은 서쪽 산의 등산로를 이용해야 한다.

예를 들어, 위의 그림의 경우 n = m = 2, x = 10, A = [40, 45] 그리고 B = [42, 42] 이다. 이 때, C = 1, D = 100 이라 하자. 상기한 모든 규칙을 만족하며 길이가 1이상 100이하인 등산 계획은 총 12가지 있다:

• 총 길이가 40이상 45이하인 등산 계획은 4가지 존재한다 (네개의 등산로 중 하나를 이용하면 된다).
• 총 길이가 92이상 97이하인 등산 계획은 8가지 존재한다 (각 산에서 등산로 하나씩을 택한 후, 등산할 순서를 정하면 된다).

입력으로 n, m, x, C, D, 그리고 A, B가 주어졌을 때, Albert를 도와 총 몇가지 방법으로 등산 계획을 세울 수 있는지 구해보자.

입력 첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스는 세줄에 걸쳐 주어진다.

첫 줄에는 n, m, x, C, D가 공백으로 구분되어 주어진다.

둘째 줄에는 동쪽 하이킹 코스 길이를 나타내는 n개의 정수가 공백으로 구분되어 주어진다.

셋째 줄에는 서쪽 하이킹 코스 길이를 나타내는 m개의 정수가 공백으로 구분되어 주어진다.

각 테스트 케이스의 정답을 각 줄에 출력한다. 단, 정답이 매우 클 수 있으므로 109+7로 나눈 나머지를 출력한다.

• 1 ≤ T ≤ 5
• 1 ≤ n, m ≤ 18
• 1 ≤ x ≤ 108
• ​1 ​≤ C ≤ D ≤ 109
• 1 ​​≤ 각 등산로의 길이 ≤ 108