Pitmutation

시간 제한2초메모리 제한1024 MB

요약

두 선수가 카드 한 장씩 내어 높은 쪽이 점수를 얻는 게임에서, 알려지지 않은 카드 배치 중 첫 번째 선수가 정확히 S점을 얻는 경우의 수를 센다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 조합론, 수학, 구현
정답자: 아직 제출이 없습니다

문제

Pitmuation is a two player card game, where each player has a deck of $N$ cards numbered from $1$ to $N$ . The two players shuffle their decks and they put the cards on the table one by one. At each step, the player with the higher card wins one point. If the two cards are equal, there are no points awarded. The game ends after $N$ steps, when all the cards have been used.

For some indices between $1$ and $N$ you know the cards of the first player, and for the other indices you know the cards of the second player.

Given the size of the decks $N$ , an integer $S$ and the known cards for the two players, determine the number of configurations of the unknown cards where the first player is awarded a total of exactly $S$ points.

입력

The first line contains two integers $N$ and $S$ .

The second line contains $N$ integers between $0$ and $N$ , corresponding to the first player. The $0$ s represent unknown cards, while the other values represent known cards.

The third line contains $N$ integers corresponding to the cards of the second player, in the same manner.

출력

Output the answer modulo $10^9+7$ .

제한

$0≤S\<N≤300$

예제1

예제 1
입력
```
4 2
4 2 0 0
0 0 4 2
```
예상 출력
```
2
```