#214935. [ICPC 2022 Yokohama R] Quiz Contest

The final round of the annual World Quiz Contest is now at the climax!

In this round, questions are asked one by one, and the competitor correctly answering the goal number of questions first will be the champion. Many questions have already been asked and answered. The numbers of questions correctly answered so far by competitors may differ, and thus the numbers of additional questions to answer correctly to win may be different.

The questions elaborated by the judge crew are quite difficult, and the competitors have completely distinct areas of expertise. Thus, for each question, exactly one competitor can find the correct answer.

Who becomes the champion depends on the order of the questions asked. The judge crew know all the questions and who can answer which, but they do not know the order of the remaining questions, as the questions have been randomly shuffled. To help the judge crew guess the champion of this year, count the number of possible orders of the remaining questions that would make each competitor win. Note that the orders of the questions left unused after the decision of the champion should also be considered.

The input consists of a single test case of the following format.

Here, is the number of competitors and is the number of remaining questions. Both and are integers satisfying . Competitors are numbered 1 through . The following line contains integers, , meaning that the number of remaining questions that the competitor can answer correctly is , where holds. The last line contains integers, , meaning that the competitor has to answer more questions correctly to win. holds.

Let be the number of question orders that make the competitor the champion. Output lines, each containing an integer. The number on the -th line should be modulo a prime number . Note that holds.

样例输入 1

2 4
2 2
1 2

样例输出 1

20
4

样例输入 2

4 6
1 1 2 2
1 1 1 2

样例输出 2

168
168
336
48

样例输入 3

4 82
20 22 12 28
20 22 7 8

样例输出 3

746371221
528486621
148054814
913602744