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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "# cook your dish here\nMOD = 10 ** 9 + 7\n \nfor t in range(int(input())):\n    N, M, K = map(int, input().split())\n    A = list(map(int, input().split()))\n    I, D = [0] * (N + 2), [0] * (N + 2)\n    for i in range(M):\n        x, L, R = input().split()\n        L, R = int(L), int(R)\n        if x == 'I':\n            I[L] += 1\n            I[R] -= 1\n        else:\n            D[L] += 1\n            D[R] -= 1\n    \n    impossibru = mx = mn = 0\n    ans = 1\n    for i in range(N):\n        I[i] += I[i - 1]\n        D[i] += D[i - 1]\n        if I[i] and D[i]:\n            impossibru = 1\n            break\n        if not I[i] and not D[i]:\n            ans = ans * (mx - mn + 1) % MOD\n            mn, mx = 1, K\n        elif I[i]:\n            mx = min(mx + 1, K)\n            mn += 1\n        elif D[i]:\n            mn = max(1, mn - 1)\n            mx -= 1\n        if mn > mx:\n            impossibru = 1\n            break\n        if A[i] != -1:\n            if not mn <= A[i] <= mx:\n                impossibru = 1\n                break\n            mn = mx = A[i]\n    ans = ans * (mx - mn + 1) % MOD\n    \n    print(0 if impossibru else ans) "
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13847