수열 섞기

수열 $C$의 구간이란 비어 있지 않은 연속 부분 수열이다. 길이가 $k$인 수열에는 $k(k+1)/2$개의 구간이 있다. 각 구간은 시작 위치와 끝 위치로 정해지기 때문이다.

수열 $[c_1, c_2, \ldots, c_k]$의 안정성은 다음 조건을 만족하는 가장 큰 정수 $s$이다. 어떤 인덱스 $i$ ($1 \le i \le k-s+1$)가 존재하여 $c_i < c_{i+1} < \cdots < c_{i+s-1}$이거나 $c_i > c_{i+1} > \cdots > c_{i+s-1}$이다. 예를 들어 $[8, 6, 1, 3, 5, 7, 4, 2]$의 안정성은 4이다. 엄격하게 단조인 구간 $[1, 3, 5, 7]$이 있고, 이보다 긴 구간은 없기 때문이다.

두 수열 $A$와 $B$의 섞임은 길이가 $|A|+|B|$인 수열이다. 이 수열은 $A$와 같은 부분 수열(연속일 필요는 없음)을 포함하고, 그 부분 수열을 제외한 나머지 원소가 순서대로 $B$를 이룬다. 예를 들어 $[1, 2, 3]$과 $[4, 5]$의 섞임에는 $[1, 4, 2, 5, 3]$, $[4, 5, 1, 2, 3]$, $[4, 1, 5, 2, 3]$이 있다. $[1, 2, 3, 4, 3]$과 $[1, 2, 3, 5, 4]$는 섞임이 아니다.

$f(A, B)$를 $A$와 $B$의 섞임 중 안정성의 최솟값이라고 하자.

길이가 각각 $n$, $m$인 두 수열 $A$, $B$가 주어진다. $f(A, B)$ 대신, $1$부터 $n+m$까지의 각 정수 $x$에 대해 $A'$는 $A$의 구간, $B'$는 $B$의 구간이고 $f(A', B') = x$를 만족하는 쌍 $(A', B')$의 개수를 구하라. 개수가 매우 클 수 있으므로 $10^9+7$로 나눈 나머지를 출력한다.

첫 줄에 두 정수 $n$, $m$ ($1 \le n, m \le 300\,000$)이 주어진다. 각각 $A$와 $B$의 길이이다.

둘째 줄에 $n$개의 정수 $A_1, A_2, \ldots, A_n$ ($1 \le A_i \le n+m$)이 주어진다.

셋째 줄에 $m$개의 정수 $B_1, B_2, \ldots, B_m$ ($1 \le B_i \le n+m$)이 주어진다.

$A$와 $B$의 모든 원소는 서로 다르다. 즉, $A$와 $B$를 이어 붙인 수열은 $1$부터 $n+m$까지의 순열이다.

$n+m$개의 정수를 공백으로 구분하여 한 줄에 출력한다. $i$번째 수는 $f(A', B') = i$를 만족하는 쌍 $(A', B')$의 개수를 $10^9+7$로 나눈 나머지이다.

$[1, 2, 5, 7, 4]$와 $[8, 3, 6]$ 전체에 대해 $f = 2$이다. 안정성이 2인 섞임의 예는 $[1, 8, 2, 5, 3, 7, 4, 6]$이다.

$[1, 2, 5, 7]$과 $[3]$에 대해서는 $f = 3$이다. 안정성이 3인 섞임의 예는 $[1, 2, 5, 3, 7]$이다. 이 쌍으로는 안정성을 3보다 작게 만들 수 없다.

$[4]$와 $[6]$에 대해서는 $f = 2$이며, 두 섞임 $[4, 6]$과 $[6, 4]$ 모두 유효한 예이다.

이 예시의 모든 구간 쌍은 안정성이 3 이하인 섞임을 만들 수 있다. 따라서 $x \ge 4$인 답은 모두 0이다.