Lucky Card Game

A group of students is playing a game with yyy. In each round, they give yyy n cards. Each card bears a number; all these numbers are lucky numbers and we denote the number on the i-th card by \(a_{i}\).

In each move, yyy can choose a card \(a_{i}\) and move forward exactly \(a_{i}\) steps, then discard that card. He wins when he has no card left. However, the opponents have placed traps on some squares, called unlucky numbers. If yyy stops on a square whose number is an unlucky number, he loses. Note: Even if he reaches the end (i.e. uses all cards) but the final position is an unlucky number, he loses.

A number may be both a lucky number (appearing on some card) and an unlucky number (a trap).

Your task is to help yyy calculate, modulo \(10^9+7\), the number of ways (i.e. orders in which to play the cards) for him to win the game.

Input Format: The input begins with an integer \(n\) denoting the number of cards, followed by a line containing \(n\) integers \(a_1, a_2, \dots, a_n\). The next line contains an integer \(m\) denoting the number of traps, followed by a line containing \(m\) integers representing the trap positions.

Note: The game starts at position \(0\).

inputFormat

The first line contains a single integer \(n\) (the number of cards).
The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) (the value on each card).
The third line contains a single integer \(m\) (the number of trap positions).
The fourth line contains \(m\) space-separated integers, each representing a trap position.

outputFormat

Output a single integer: the number of winning orders modulo \(10^9+7\).

sample

3
1 2 3
2
3 6

0