색칠

시간 제한1초메모리 제한512 MB

요약

서로 다른 색 i와 j를 고른 뒤 N개의 칸을 두 종류의 크레파스로 칠하는 방법의 수를 모두 더해 구한다.

문제

배열 게임 파티를 위해 $1$ 번부터 $N$ 번까지 번호가 붙은 $N$ 개의 칸으로 이루어진 배열을 색칠하려고 한다.

다락방에는 A와 B 두 종류의 크레파스가 있고, 각 종류마다 $M$ 개의 봉지가 있으며 $i$ 번째 봉지에는 색 $i$ 의 크레파스가 들어 있다.

각 봉지에는 두께가 서로 다른 여러 크레파스가 들어 있다.

다음과 같은 방식으로 칸을 색칠해야 한다.

먼저 A 종류에서 하나, B 종류에서 하나씩 두 개의 크레파스 봉지를 고른다. A 종류와 B 종류에서 고른 봉지의 크레파스 색은 서로 달라야 한다.
다음으로 두 봉지를 열고 그 안의 크레파스로 $N$ 개의 칸을 $1, \, 2, \, \cdots, \, N$ 순서대로 색칠한다. 어떤 칸을 건너뛰거나 한 칸을 여러 크레파스로 색칠하는 것은 금지된다. 같은 크레파스를 여러 번 사용할 수 있다.

$N$ 개의 칸을 색칠하는 방법은 몇 가지인가? 고른 두 봉지 중 하나라도 다르거나, 어떤 칸을 색칠하는 데 사용한 크레파스의 종류, 색, 두께 중 하나라도 다르면 다른 방법으로 센다.

첫째 줄에 두 정수 $N$ 과 $M$ 이 주어진다. $N$ 은 칸의 수, $M$ 은 크레파스 종류마다 있는 봉지의 수이다.

둘째 줄에 $M$ 개의 정수 $A\_1, \, A\_2, \, \cdots, \, A\_M$ 이 주어진다. $A\_i$ 는 A 종류의 $i$ 번째 봉지에 들어 있는 크레파스의 수이다.

셋째 줄에 $M$ 개의 정수 $B\_1, \, B\_2, \, \cdots, \, B\_M$ 이 주어진다. $B\_j$ 는 B 종류의 $j$ 번째 봉지에 들어 있는 크레파스의 수이다.

$N$ 개의 칸을 색칠하는 방법의 수를 $10^9+7$ 로 나눈 나머지를 출력한다.