408399: GYM103114 C Chtholly and Floating Islands

It's been over 500 years since the human race almost went extinct at the hands of the fearsome and mysterious "Beasts". The surviving races now make their homes, towns, and cities up on floating islands in the sky to keep out of reach of all but the most mobile of Beasts.

Chtholly is on the $$$1$$$-th island now, and she wants to reach the $$$n$$$-th island. Due to her flying abilities (we can think of her flying abilities as an array $$$a$$$), she can fly exactly to the $$$(j + a_i)$$$-th island when she is on the $$$j$$$-th island. For example, if she is on the $$$1$$$-th island now, and her flying ability array $$$a$$$ is $$$[1, 3]$$$, she can only reach the $$$2$$$-th island or the $$$4$$$-th island at this time.

As a clever girl, Chtholly can improve her flying abilities before starting the flight, which means she will add some integers to her ability array $$$a$$$ when she is on the $$$1$$$-th island. For example, if her original flying ability $$$a$$$ is $$$[1, 3]$$$, and she adds $$$[2, 4]$$$ to $$$a$$$. Now her ability array is $$$[1, 2, 3, 4]$$$, she can reach one island from the $$$2$$$-th island to the $$$5$$$-th island at this time. All the abilities Chtholly has and will improve are different. In other words, they are all distinct integers.

Now, Chtholly has known the abilities she can improve. Obviously, the number of ways she can reach the $$$n$$$-th island will be affected by her choice. As a curious girl, Chtholly wants to know in how many different ways she can reach the $$$n$$$-th island if she choose some abilities to improve. She will give you $$$q$$$ choices, and you should tell her the answer to each choice.

The way records the flying abilities Chtholly used in turn. A way $$$x$$$ is different from a way $$$y$$$ if their lengths are different or there exists an index $$$i$$$ such that $$$x_i \neq y_i$$$. You can see a specific example in the notes.

The first line contains three integer $$$n$$$ ($$$1 \leq n \leq 10^4$$$), $$$m$$$ ($$$1 \leq m \leq 10$$$), and $$$k$$$ ($$$1 \leq k \leq 10$$$) — the index of island Chtholly wants to reach, the number of abilities she has and the number of abilities she can improve.

The second line contains $$$m$$$ space-separated integers $$$a_1$$$, $$$a_2$$$, $$$\dots$$$, $$$a_m$$$ $$$(0 \leq a_i \leq 10^4)$$$ — the ability Chtholly has.

The third line contains $$$k$$$ space-separated integers $$$b_1$$$, $$$b_2$$$, $$$\dots$$$, $$$b_k$$$ $$$(0 \leq b_i \leq 10^4)$$$ — the ability Chtholly can improve. It is guaranteed that all integers in $$$a$$$ and $$$b$$$ are different.

The next line contains one integer $$$q$$$ $$$(1 \leq q \leq 10^4)$$$ — the number of choices Chtholly wants to know.

Each of the next $$$q$$$ lines contains an integer $$$c$$$ $$$(0 \leq c \leq k)$$$, followed by $$$c$$$ distinct integers $$$d_1$$$, $$$d_2$$$, $$$\dots$$$, $$$d_c$$$ ($$$1 \leq d_i \leq k$$$)separated by spaces — indexes of abilities Chtholly improve on this choice.

For each choice, print the number of different ways Chtholly can reach the n-th island. Since the answer can be very huge, you have output it modulo $$$10^9 + 7$$$.

4 1 1
2
1
2
0
1 1

0
3

1 1 1
2
3
2
0
1 1

1
1

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

5
7
6
8

In the first example, the situation is as follows:

• In the first choice, Chtholly's ability array is $$$[2]$$$, she can only reach the $$$1$$$-th island and the $$$3$$$-th island in islands with indexes less than or equal to $$$4$$$.
• In the second choice, Chtholly's ability array is $$$[1, 2]$$$, she can reach the $$$4$$$-th island in three ways.$$$[2, 1]$$$, $$$[1, 2]$$$, and $$$[1, 1, 1]$$$.