connect

IATI 2022 때문에 전국을 돌아다니는 일이 많아져서, 규쇼의 관광 가이드 회사에는 또 질문이 몰렸다. 이 회사가 담당하는 지역은 1번부터 N번까지 번호가 붙은 N개의 도시로 이루어져 있다. 도시 사이에는 1번부터 M번까지 번호가 붙은 M개의 직접 도로가 있으며, 각 도로는 서로 다른 두 도시를 잇는다. 두 도시 사이에 같은 방향의 직접 도로가 둘 이상 있을 수도 있다.

배차 부서에는 버스 기사들로부터 다음과 같은 질문이 자주 들어온다. "도로 하나가 막혀도 도시 A에서 도시 B로 갔다가 다시 도시 A로 돌아올 수 있는가?"

규쇼는 여러분이 경험 많은 프로그래머라는 것을 알고 있어서, 이런 질문에 답하는 프로그램 connect를 작성해 달라고 부탁했다.

첫 줄에 도시의 수 N과 직접 도로의 수 M이 양의 정수로 주어진다. 이어지는 M개의 줄에는 도시 A에서 도시 B로 가는 직접 도로가 있음을 뜻하는 양의 정수 A와 B가 주어진다.

다음 줄에는 질문의 개수 Q가 양의 정수로 주어진다. 이어지는 Q개의 줄에는 도시 A와 B에 대한 질문이 하나씩 주어진다.

질문이 너무 많을 때는 순서가 없는 도시 쌍 (A, B)마다 답을 구하는 편이 낫다. Q = 0이면 (1,1), (1,2), (1,3), ..., (1,N), (2,2), (2,3), ..., (2,N), (3,3), ..., (N,N) 순서대로 답을 구해야 한다.

각 질문에 다음 규칙에 따라 수를 정한다.

• $0$: 도로를 하나도 닫지 않아도, 두 도시 중 한쪽 방향으로 가는 경로가 없다.
• $M+1$: 어느 도로를 닫더라도, 두 도시 사이를 양방향 모두 항상 오갈 수 있다.
• $1$부터 $M$까지의 수: 그 번호의 도로를 닫으면 한쪽 방향의 경로가 사라진다. 이런 도로가 여럿이면 번호가 가장 작은 도로를 쓴다.

얻은 수를 $s_1, s_2, \dots, s_K$라 하자. 여기서 $Q \neq 0$이면 $K = Q$이고, $Q = 0$이면 $K = \frac{N \times (N+1)}{2}$이다. 다음 값을 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다. 단, $B = 2 \times 10^5$이다.

$P = s_1 \times B^{K-1} + s_2 \times B^{K-2} + \cdots + s_K \times B^0$

• $2 \le N \le 2000$
• $1 \le A, B \le N$
• $1 \le M \le 10^5$
• $0 \le Q \le 10^5$