8832번 - Reszty 다국어

문제

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.

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:

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).

제한

힌트