Hektor bardzo lubi zadania programistyczne związane z problemem wydawania reszty, czy też ogólnie konstruowaniem sum pieniędzy przy użyciu określonych nominałów. Jakiś czas temu zauważył, że wiele zadań ma proste rozwiązania w sytuacji, w której każdy kolejny nominał jest wielokrotnością poprzedniego.</p>

Spróbuj rozwiązać następujący problem - znając wartości kolejnych nominałów i mając określoną liczbę banknotów każdego z nich, ile różnych kwot potrafimy uzyskać?

Będziemy rozważać tylko zestawy nominałów, w których każdy kolejny nominał jest wielokrotnością poprzedniego.

"Kwotę da się uzyskać" wtedy i tylko wtedy, kiedy istnieje podzbiór posiadanych banknotów o wartości sumującej się do danej kwoty.

Ponieważ liczba osiągalnych kwot może być całkiem duża, należy wypisać jej resztę z dzielenia przez 10⁹ + 7.

입력 형식

W pierwszej linii wejścia znajduje się liczba zestawów testowych Z ( 1 <= Z <= 10 ). Następnie opisywane są kolejne zestawy:</p>

Pierwsza linia zawiera liczbę naturalną N 

/advanced/langs/en.js" type="text/javascript"> ( 1 <= N <= 1000) - liczbę nominałów.

Druga linia zawiera N liczb naturalnych, i-ta z nich to x_i ( 1 <= x_i <= 10⁹ ) - liczba banknotów i-tego nominału.

Trzecia linia zawiera N-1 liczb naturalnych, i-ta z nich to d_i (1 <= d_i <= 10⁹), co oznacza, że wartość i+1 nominału = d_i * wartość i-tego nominału. Pierwszy z nominałów ma wartość 1.

출력 형식

Dla każdego przypadku testowego wypisz liczbę osiągalnych kwot (modulo 10⁹ + 7).

예제 입력

2
3 
1 1 1 
2 3 
2 
2 2 
2

예제 출력

8
7