만들 수 있는 금액의 개수

헥토르는 거스름돈 문제, 더 일반적으로는 정해진 화폐 단위(액면가)들로 금액을 만드는 문제를 좋아한다. 그는 각 액면가가 바로 앞 액면가의 배수인 경우에 많은 문제들이 간단하게 풀린다는 사실을 발견했다.

다음 문제를 풀어 보자. 연속한 액면가들의 값과 각 액면가의 지폐 개수가 주어질 때, 서로 다른 금액을 몇 가지나 만들 수 있는가?

단, 각 액면가가 바로 앞 액면가의 배수가 되는 액면가 집합만 다룬다.

어떤 금액을 "만들 수 있다"는 것은, 가지고 있는 지폐들의 어떤 부분집합의 값의 합이 그 금액과 같아지는 경우를 뜻한다.

만들 수 있는 금액의 수가 매우 커질 수 있으므로, 그 값을 $10^9 + 7$ 로 나눈 나머지를 출력한다.

첫 번째 줄에 테스트 케이스의 수 $Z$ ($1 \le Z \le 10$) 가 주어진다. 이어서 각 테스트 케이스가 다음과 같이 주어진다.

각 테스트 케이스의 첫 번째 줄에는 액면가의 개수를 나타내는 자연수 $N$ ($1 \le N \le 1000$) 이 주어진다.

두 번째 줄에는 $N$ 개의 자연수가 주어지며, $i$ 번째 수 $x_i$ ($1 \le x_i \le 10^9$) 는 $i$ 번째 액면가의 지폐 개수이다.

세 번째 줄에는 $N-1$ 개의 자연수가 주어지며, $i$ 번째 수 $d_i$ ($1 \le d_i \le 10^9$) 는 $i+1$ 번째 액면가의 값이 $d_i \times$ ($i$ 번째 액면가의 값) 임을 뜻한다. 첫 번째 액면가의 값은 $1$ 이다.

각 테스트 케이스마다 만들 수 있는 서로 다른 금액의 수를 $10^9 + 7$ 로 나눈 나머지를 한 줄에 하나씩 출력한다.