Block Partitioning with Allowed Sizes

You are given a sequence of length \(n\). Two people, PinkRabbit and NaCly_Fish, each specify a (possibly repeated) list of allowed block lengths. PinkRabbit permits partitioning the sequence only into blocks whose lengths belong to his list and NaCly_Fish permits only those block lengths in his list. In order for xht37 to satisfy both requirements simultaneously, he may only use those block lengths which are allowed by both.

Your task is to count the number of different ways to partition the sequence into blocks such that each block's length is an element of the intersection of the two allowed lists. Two partitions are considered different if the positions of the cuts (or, equivalently, the sequence of block lengths) differ.

Since the answer may be very large, output the result modulo \(10^9+7\).

The problem can be solved using dynamic programming. Let \(dp[i]\) denote the number of ways to partition a sequence of length \(i\) using the allowed block lengths. The recurrence is given by:

[ dp[i] = \sum_{\ell \in S,\ i\ge \ell} dp[i-\ell], \quad dp[0] = 1, ]

where \(S\) is the set of allowed block lengths (i.e. the intersection of the two given lists).

inputFormat

The input consists of five lines:

• Line 1: An integer \(n\) representing the length of the sequence.
• Line 2: An integer \(PR\), the number of block lengths allowed by PinkRabbit.
• Line 3: \(PR\) space-separated integers representing the allowed block lengths by PinkRabbit.
• Line 4: An integer \(NF\), the number of block lengths allowed by NaCly_Fish.
• Line 5: \(NF\) space-separated integers representing the allowed block lengths by NaCly_Fish.

outputFormat

Output a single integer — the number of possible partitioning schemes, taken modulo \(10^9+7\).

sample

5
3
1 2 3
3
1 2 4

8