Number of Obtainable Amounts

Hektor really enjoys programming problems about making change, or more generally about forming sums of money from a given set of denominations. Some time ago he noticed that many such problems become easy when every denomination is a multiple of the one before it.

Solve the following problem: given the values of consecutive denominations and how many banknotes of each you hold, how many distinct amounts can you form?

We only consider sets of denominations in which each denomination is a multiple of the previous one.

An amount "can be formed" if and only if some subset of the banknotes you hold has values that sum to exactly that amount.

Because the number of achievable amounts can be very large, print it modulo $10^9 + 7$.

The first line contains the number of test cases $Z$ ($1 \le Z \le 10$). Each test case then follows.

The first line of a test case contains a natural number $N$ ($1 \le N \le 1000$), the number of denominations.

The second line contains $N$ natural numbers; the $i$-th of them, $x_i$ ($1 \le x_i \le 10^9$), is the number of banknotes of the $i$-th denomination.

The third line contains $N-1$ natural numbers; the $i$-th of them, $d_i$ ($1 \le d_i \le 10^9$), means that the value of the $(i+1)$-th denomination equals $d_i \times$ (the value of the $i$-th denomination). The first denomination has value $1$.

For each test case, print the number of distinct achievable amounts modulo $10^9 + 7$, one per line.