시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB33121134.375%

문제

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.

예제 입력 1

1 3
1 2 3
2 3 1

예제 출력 1

24

출처