Chef had an array A with length N, but some of its elements got lost. Now, each element of this array is either unknown (denoted by -1) or a positive integer not exceeding K.
Chef decided to restore the array A by replacing each unknown element by a positive integer not exceeding K.
However, Chef has M restrictions that must hold for the restored array. There are two types of restrictions:

- I L R, meaning that for each i such that L < i ≤ R, the condition Ai - Ai-1 = 1 should be satisfied.
- D L R, meaning that for each i such that L < i  ≤ R, the condition Ai - Ai-1 = -1 should be satisfied.

Chef would like to know the number of ways to restore the array while satisfying all restrictions, modulo 109+7.

-----Input-----
- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains three space-separated integers N, M and K.
- The second line contains N integers A1, A2, ..., AN.
- Each of the following M lines contains one restriction in the form I L R or D L R.

-----Output-----
For each test case, print a single line containing one integer - the number of ways to restore the array modulo 109+7.

-----Constraints-----
- 1 ≤ T ≤ 10
- 1 ≤ N, M ≤ 100,000
- 1 ≤ K ≤ 1,000,000,000
- 1 ≤ L < R ≤ N
- 1 ≤ Ai ≤ K or Ai = -1 for each valid i
- 1 ≤ sum of N over all test cases ≤ 500,000
- 1 ≤ sum of M over all test cases ≤ 500,000

-----Example-----
Input:

3
4 2 10
2 3 5 4
I 1 2 
D 3 4
5 2 10
-1 -1 -1 -1 -1
I 1 3
D 3 5
6 2 2
-1 -1 -1 -1 -1 -1
I 1 4
D 4 6

Output:

1
8
0

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
# cook your dish here
MOD = 10 ** 9 + 7
 
for t in range(int(input())):
    N, M, K = map(int, input().split())
    A = list(map(int, input().split()))
    I, D = [0] * (N + 2), [0] * (N + 2)
    for i in range(M):
        x, L, R = input().split()
        L, R = int(L), int(R)
        if x == 'I':
            I[L] += 1
            I[R] -= 1
        else:
            D[L] += 1
            D[R] -= 1
    
    impossibru = mx = mn = 0
    ans = 1
    for i in range(N):
        I[i] += I[i - 1]
        D[i] += D[i - 1]
        if I[i] and D[i]:
            impossibru = 1
            break
        if not I[i] and not D[i]:
            ans = ans * (mx - mn + 1) % MOD
            mn, mx = 1, K
        elif I[i]:
            mx = min(mx + 1, K)
            mn += 1
        elif D[i]:
            mn = max(1, mn - 1)
            mx -= 1
        if mn > mx:
            impossibru = 1
            break
        if A[i] != -1:
            if not mn <= A[i] <= mx:
                impossibru = 1
                break
            mn = mx = A[i]
    ans = ans * (mx - mn + 1) % MOD
    
    print(0 if impossibru else ans) 

MOD = 10 ** 9 + 7
for t in range(int(input())):
    N, M, K = map(int, input().split());    A = list(map(int, input().split()));    I, D = [0] * (N + 2), [0] * (N + 2)
    for i in range(M):
        x, L, R = input().split();        L, R = int(L), int(R)
        if x == 'I':I[L] += 1;I[R] -= 1
        else:D[L] += 1;D[R] -= 1    
    impossibru = mx = mn = 0;ans = 1
    for i in range(N):
        I[i] += I[i - 1];D[i] += D[i - 1]
        if I[i] and D[i]:impossibru = 1;break
        if not I[i] and not D[i]:ans = ans * (mx - mn + 1) % MOD;mn, mx = 1, K
        elif I[i]:mx = min(mx + 1, K);mn += 1
        elif D[i]:mn = max(1, mn - 1);mx -= 1
        if mn > mx:impossibru = 1;break
        if A[i] != -1:
            if not mn <= A[i] <= mx:impossibru = 1;break
            mn = mx = A[i]
    ans = ans * (mx - mn + 1) % MOD    
    print(0 if impossibru else ans) 

# cook your dish here
MOD = 10 ** 9 + 7
 
for t in range(int(input())):
    N, M, K = map(int, input().split())
    A = list(map(int, input().split()))
    I, D = [0] * (N + 2), [0] * (N + 2)
    for i in range(M):
        x, L, R = input().split()
        L, R = int(L), int(R)
        if x == 'I':
            I[L] += 1
            I[R] -= 1
        else:
            D[L] += 1
            D[R] -= 1
    
    impossibru = mx = mn = 0
    ans = 1
    for i in range(N):
        I[i] += I[i - 1]
        D[i] += D[i - 1]
        if I[i] and D[i]:
            impossibru = 1
            break
        if not I[i] and not D[i]:
            ans = ans * (mx - mn + 1) % MOD
            mn, mx = 1, K
        elif I[i]:
            mx = min(mx + 1, K)
            mn += 1
        elif D[i]:
            mn = max(1, mn - 1)
            mx -= 1
        if mn > mx:
            impossibru = 1
            break
        if A[i] != -1:
            if not mn <= A[i] <= mx:
                impossibru = 1
                break
            mn = mx = A[i]
    ans = ans * (mx - mn + 1) % MOD
    
    print(0 if impossibru else ans)