24172번 - Coloring 다국어

문제

You will color an array consisting of $N$ cells numbered 1ドル$ to $N$ for the array game party.

In the attic, there are two types of crayons, A and B, and $M$ bags for each type, which the $i$-th bag has crayons with color $i$.

In each bag, there are several crayons having pairwise different thicknesses.

You have to color the cells like the following:

• First, choose two crayon bags, one from type A and the other from B. The color of the crayons in bags from types A and B must be different.
• Second, open the two bags and use the crayons in them to color the $N$ cells(in the order of 1,ドル ,円 2, ,円 \cdots, ,円 N$). Skipping coloring some cells or using multiple crayons to color a single cell is forbidden. You can use a single crayon as many times as you want.

How many ways are there to color the $N$ cells? Consider as a different way if at least one of the two bags you chose is different or the crayon you used to color a particular cell has a different type, color, or thickness.

입력

The first line contains two integers $N$ and $M$ — the number of cells and the number of bags of each crayon type, respectively.

The second line contains $M$ integers $A_1, ,円 A_2, ,円 \cdots, ,円 A_M,ドル where $A_i$ is the number of crayons in the $i$-th bag of type A.

The third line contains $M$ integers $B_1, ,円 B_2, ,円 \cdots, ,円 B_M,ドル where $B_j$ is the number of crayons in the $j$-th bag of type B.

출력

Print the number of ways to color the $N$ cells, modulo 10ドル^9+7$.

제한

• 1ドル \le N \le 3 \times 10^2$
• 1ドル \le M \le 10^5$
• 1ドル \le A_i, ,円 B_j \le 10^9$ (1ドル \le i, ,円 j \le M$)
• All values in input are integers.

힌트