Hektor i Wiktor realizują wraz ze swym kolegą Sławkiem projekt semestralny z fizyki. Podczas gdy dwaj pierwsi wzięli na siebie przeprowadzenie eksperymentów, Sławkowi przypadło zadanie przygotowania slajdów do prezentacji wyników.</p>

Sławek przygotował szkic prezentacji N kolejno ponumerowanych slajdów, a Hektor i Wiktor uszeregowali je od najmniej, do najbardziej ich zdaniem istotnych - każdy z nich osobno. Teraz pozostaje tylko wybrać slajdy do ostatecznej prezentacji. Chłopcy umówili się, że slajdy w ostatecznej prezentacji będą podzbiorem slajdów z propozycji Sławka i że pokażą je w oryginalnej kolejności. Dodatkowo chcieliby, żeby każdy kolejny slajd w ostatecznej prezentacji był ważniejszy od poprzedniego - i to zarówno według klasyfikacji Hektora jak i Wiktora.

Ile różnych zestawów slajdów spełnia te warunki?

입력 형식

W pierwszej linii znajduje się liczba naturalna Z ( 1 <= Z <= 10 ) oznaczająca liczbę zestawów testowych. Następnie opisywane są kolejne zestawy.</p>

W pierwszej linii pojedynczego zestawu testowego znajduje się jedna liczba całkowita N ( 1 <= N <= 50 000 ), określająca liczbę slajdów przygotowanych przez Sławka. W drugiej i trzeciej linii znajduje się po N dodatnich liczb całkowitych nie większych niż N, oznaczające kolejności slajdów wg Hektora i Wiktora. W każdej z tych dwóch linii wszystkie N liczb są różne.

출력 형식

Dla każdego zestawu testowego należy w jednej linii wypisać jedną liczbę - resztę z dzielenia przez 1 000 000 007 liczby różnych zestawów slajdów spełniających nakreślone warunki.

예제 입력

3
3
1 2 3
1 3 2
4
3 1 2 4
1 3 2 4
5
4 2 5 1 3
5 4 3 2 1

예제 출력

5
9
5

힌트

W pierwszym zestawie testowym prawidłowe zestawy slajdów to (1), (2), (3), (1,2) i (1,3).