Teacher! Are we gonna have Cirno as a snack?
Even though Cirno, the circle-nine, looks really tasty,
I have to control myself and now eat Kanako's rice gruel instead.
I'll eat her after she gets fatter!
I'm aiming for the top of the food chain,
So today I'm training again,
Frog-leaping up the shrine stairs~!
-- Moriya Suwako Kero ⑨ Destiny
Moriya Suwako is training by frog-leaping up and down the shrine stairs. The staircase consists of N steps. On the way up, Suwako can take any of some specified steps at a time. On the way down, she can take any of some other specified steps at a time, and she can only walk on the steps she used on the way up. How many different paths are available for her training?
There are multiple test cases. Process to the End of File.
Each test case contains three lines of integers as follows:
N
U A
1 A
2 ... A
UD B
1 B
2 ... B
DN is the total number of steps. A
i is the number of steps that can be taken on the way up, all A
is are different. B
i is the number of steps that can be taken on the way down, all B
is are different.
1 ≤ N ≤ 10
181 ≤ U, D ≤ 50
1 ≤ A
i, B
i ≤ 200
For each test case, output the number of paths module 1,000,000,007.