F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
 Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Jumping Frog

Time Limit: 21000/21000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 639    Accepted Submission(s): 163


Problem Description

                                     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?
 

Input
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
 

Output
For each test case, output the number of paths module 1,000,000,007.
 

Sample Input
3
2 1 2
4 1 2 3 4
5
2 1 2
4 1 2 3 4
 

Sample Output
8
52
 

Author
Zejun Wu (watashi)
 

Source
2013 Multi-University Training Contest 9
 

Statistic | Submit | Discuss | Note
Home | Top Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2025 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2025-04-01 06:23:59, Gzip enabled 		Administration