malware 박멸하기

Albert는 $N$ 대의 컴퓨터로 구성된 클러스터를 갖고 있는데, 현재 모든 컴퓨터는 malware 에 감염된 상태이다 (편의상 컴퓨터는 $1, 2, \dots, N$ 으로 번호가 붙어있다).

현재 총 $M$ 쌍의 컴퓨터가 방화벽 없는 "연결망"을 통해 연결되어있는데, 이를 통해 malware 가 계속 전파될 수 있다. 구체적으로, $X, Y$ 크기가 $M$ 인 정수 배열일 때 (각 $X_i, Y_i$ 값은 컴퓨터 번호이다), 매일 저녁에 아래와 같은 일이 일어난다:

• $1 \le i \le M$ 인 $i$ 에 대하여, 저녁 6시가 되는 순간 컴퓨터 $X_i$ 가 감염된 상태라면, 컴퓨터 $Y_i$ 는 6시 직후에 감염된 상태로 바뀐다.
• 이 전파는 $M$ 쌍에 대해 동시에 일어나기 때문에, 새로 감염된 컴퓨터가 다른 컴퓨터를 즉시 감염시킬 수는 없다.

예를 들어 아래 그림은 $N = 5, M = 6$, $X = [5, 3, 2, 1, 5, 3]$, $Y = [4, 2, 4, 2, 2, 1]$ 인 경우를 나타낸다.

Albert는 급조한 소프트웨어를 이용하여 모든 컴퓨터의 데이터를 스캔한 후 주기적으로 malware를 박멸해보려고 한다.

1. 이 소프트웨어는 한 번 가동하면 총 $P$ 일 동안 작동하며, 각 컴퓨터의 malware를 정확히 한 번씩 박멸한다 (이 때 $P \ge N$).
2. $1 \le i \le N$ 인 $i$ 에 대하여, 컴퓨터 $i$ 는 $C_i$ 번째 날 오전 10시에 처리되며, malware는 해당 컴퓨터에서 완전히 박멸된다 (다만, 같은 날 저녁 6시에 다른 컴퓨터가 다시 컴퓨터 $i$ 를 감염시킬 수도 있다.)
3. 위 과정을 $P$일 단위로 무한히 반복한다. 즉, 컴퓨터 $i$ 는 $C_i$ 번째 날 오전 10시에 처리되고, $P$ 일 후인 $C_i + P$ 번째 날 다시 처리되고, $C_i + 2 \cdot P$ 번째 날 처리되는 등 이 과정이 $P$일 주기로 반복된다.

예를 들어 위와 같은 클러스터가 있고, $P = 7$ 이고 $C = [1, 4, 2, 6, 7]$ 이라 하자. 이 때 아래와 같은 순서로 소프트웨어가 동작한다.

Albert는 매일 밤 11시에 malware에 감염된 컴퓨터의 수를 측정하는 버릇이 있는데, $j$ 번째 날 밤 11시를 기준으로 malware에 감염된 컴퓨터의 수를 $S_j$ 라 하자. Albert는 1일째부터 $K$ 일째 밤까지 이 값을 측정하여, 그 총합인 $\sum_{1 \le j \le K} S_j$ 가 무엇인지 알고 싶다. 위의 예제에서 $K = 11$ 이라면 $S = [5, 4, 4, 4, 4, 4, 3, 2, 2, 2, 1]$ 이 되므로 정답은 35가 된다.

입력으로 $N, M, C, X, Y, P, K$가 주어졌을 때, $\sum_{1 \le j \le K} S_j$ 값을 구해보자.

입력 첫 줄에 테스트 케이스의 수 $T$ 가 주어진다.

각 테스트 케이스의 첫 줄에는 $N, M, P, K$ 가 공백으로 구분되어 주어진다. 둘째 줄에는 배열 $C$ 의 값인 $N$ 개의 정수가 공백으로 구분되어 주어진다. 다음 $M$ 줄에 걸쳐 각 줄에 한 쌍의 정수가 공백으로 구분되어 주어지는데, 이는 방화벽 없이 연결된 컴퓨터 쌍 $X_i, Y_i$ 를 나타낸다.

각 테스트 케이스의 정답인 $\sum_{1 \le j \le K} S_j$ 값을 $10^9 + 7$ 로 나눈 나머지를 각 줄에 출력한다.

• $1 \le T \le 15$
• $1 \le N \le 50,000$
• $1 \le M \le \min(\binom{N}{2}, 200,000)$
• $N \le P \le 150,000$
• $1 \le K \le 1,234,567,890$
• $1 \le i \le N$ 인 각 $i$에 대하여: $1\le C_i \le P$
• $C_i = C_j$ 이면서 $i \neq j$ 인 경우는 없다 (즉, 배열 $C$ 의 원소는 고유하다)
• $1 \le i \le M$ 인 각 $i$에 대하여:
  • $1 \le X_i, Y_i \le N$ 이고 $X_i \neq Y_i$
• $(X_i, Y_i) = (X_j, Y_j)$ 이면서 $i \neq j$ 인 경우는 없다 (즉, $X \times Y$ 의 원소는 고유하다)