1291: 계단식 수열 합치기

두 수열 A와 B가 '계단식 수열'이다.

계단식 수열은 수열의 각 원소가 바로 이전 원소보다 D를 초과하여 크지 않은(a_i−1+D) 수열을 말한다.

예를 들어 D=3일 때, [5, 8, 7, 10]은 계단식 수열이지만 [5, 9, 7, 10]은 9가 5보다 3을 초과하여 크므로 계단식 수열이 아니다.

길이 N의 계단식 수열 A와 길이 M의 계단식 수열 B가 주어진다.

이 두 수열을 합쳐서 새로운 수열 C를 만들려고 한다.

수열을 합칠 때는 각 수열 A와 B의 원래 원소 순서는 그대로 유지되어야 한다.

예를 들어 A=[1, 3], B=[2, 4]를 합친다면 C=[1, 2, 3, 4]나 C=[2, 1, 3, 4]는 가능하지만, C=[3, 1, 2, 4]는 A의 원소 순서(1 다음 3)가 유지되지 않아 불가능하다.

이렇게 만들어진 합친 수열 C 역시 D-계단식 수열이어야 한다.

주어진 두 계단식 수열 A와 B를 합쳐서 만들 수 있는 새로운 D-계단식 수열 C의 경우의 수는 총 몇 가지인지 구하시오.

경우의 수가 매우 클 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.

• 첫째 줄에 두 수열의 길이 N, M과 계단식 수열의 조건 D가 공백으로 주어진다. (1 ≤ N, M ≤ 2,000, 0 ≤ D ≤ 1,000,000,000)

• 둘째 줄에 수열 A의 원소 A_1,A_2,dots,A_N이 공백으로 주어진다.

• 셋째 줄에 수열 B의 원소 B_1,B_2,dots,B_M이 공백으로 주어진다.

• (1 ≤ A_i,B_i ≤ 1,000,000,000)

• 입력으로 주어지는 수열 A와 B는 그 자체로 이미 D-계단식 수열임이 보장된다.

• 조건을 만족하는 새로운 수열 C를 만드는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.

2 2 1
10 11
9 10

3