2015
09-17

Jumping Frog

                                     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 A1 A2 … AU
D B1 B2 … BD
N is the total number of steps. Ai is the number of steps that can be taken on the way up, all Ais are different. Bi is the number of steps that can be taken on the way down, all Bis are different.

1 ≤ N ≤ 1018
1 ≤ U, D ≤ 50
1 ≤ Ai, Bi ≤ 200

There are multiple test cases. Process to the End of File.
Each test case contains three lines of integers as follows:
N
U A1 A2 … AU
D B1 B2 … BD
N is the total number of steps. Ai is the number of steps that can be taken on the way up, all Ais are different. Bi is the number of steps that can be taken on the way down, all Bis are different.

1 ≤ N ≤ 1018
1 ≤ U, D ≤ 50
1 ≤ Ai, Bi ≤ 200

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

8
52