Zelda is given integers () and she has two sequences and of length , indexed from to . Zelda will use these two sequences to play a game, which proceeds as follows:
Uniformly and randomly select an integer from the interval .
For , execute the following operations in order: first let , then let .
Zelda wants to know the expected value of the final .
Unfortunately, Zelda has forgotten some of the integers in sequences and , so she wants you to calculate the expected value of the final when all forgotten integers are also uniformly and randomly selected from the interval , modulo . Since Zelda will play the game multiple times, you need to answer queries for multiple different values of .
输入格式
The first line of the input contains three integers (, ), indicating the length of the two sequences, the number of times Zelda plays the game, and the lower bound for uniform random selections.
The next line of the input contains non-negative integers ( or ). means the integer was forgotten by Zelda.
The next line of the input contains non-negative integers ( or ). means the integer was forgotten by Zelda.
The next line of the input contains integers (), indicating the value of each time Zelda plays a game.
输出格式
The output contains lines, where the -th line contains a single integer representing the answer for the -th game, modulo .
Formally, let . It can be shown that the answer can be expressed as an irreducible fraction , where and are integers and . Output the integer equal to . In other words, output such an integer that and .
样例
样例输入 1
2 5 1
2 2
0 1
1 2 3 50 538
样例输出 1
1
750000007
888888897
857200008
228862927
样例输入 2
3 5 2
3 3 0
3 0 0
2 3 4 50 519
样例输出 2
2
750000008
962962973
798646858
311741862
数据范围与提示
In the first example, sequences and (where indicates a forgotten value), and there are queries.
In the first query, , so always. The game process is as follows:
Initially, .
Do operations with , first, and then .
Do operations with , first, and then .
So the answer for the first query is .
In the second query, , so should be selected from .
, becomes after all operations.
, becomes after all operations.
, becomes after all operations.
, becomes after all operations.
Each case has probability , so the answer for the second query is .
