28699번 - DAGame Extreme

문제

우“영”이와 현“철”이는 영철버거 돈 마리네 세트를 걸고 내기를 한다. 현철이는 <제2회 고려대학교 MatKor Cup: 2023 Winter>의 DAGame에서 다음과 같은 게임을 만들었다.

$N$개의 노드와 $M$개의 간선으로 이루어진 DAG(사이클이 없는 방향 그래프)가 있다. $K$개의 말이 각각 노드 중 하나에 놓여 있다. 모든 노드마다 놓을 수 있는 말의 개수에는 제한이 없으며, 각각의 말은 색깔을 가지고 있다. 또한, 각 색깔은 1ドル$ 이상 $N$ 이하의 정수로 표현된다. 모든 색깔에 대하여 특정 색깔을 가진 말은 최대 두 개뿐이다. 우영이부터 차례를 번갈아 가며 다음 행동을 취한다.

• 한 개의 말을 선택하여 그래프 상에서 나가는 방향의 간선을 골라 다음 노드로 옮긴다.
• 같은 색깔의 말이 같은 노드에 존재하는 순간 서로 업혀 그다음부터 같이 움직이게 되고, 색이 다른 말끼리는 항상 영향을 주지 않는다.

게임 시작 전부터 말이 업히는 경우가 존재할 수도 있다. 자신의 차례에 더이상 행동을 할 수 없는 사람이 지게 된다.

이 내기가 고려대학교의 명물이 되자, 영철버거를 찾는 손님들이 누가 이길지를 두고 내기를 하기 시작했다. 하지만 언제나 정답을 예측할 수 있으므로 불공평하다는 단점이 있었다.

이를 알게 된 현철은 각 말의 위치를 색깔에 따라 다른 암호를 사용하여 암호화하였으며, 색깔 $c$에 대응하는 암호는 두 정수 $H_0(c) ,H_1(c)$로 표현할 수 있다. $H_0(c) ,H_1(c)$은 모두 256ドル$ 미만의 음이 아닌 정수이며 서로 다른 $c$에 대하여 같은 값을 가질 수 있다. $A$는 0ドル$ 이상 256ドル$ 미만의 정수로 이루어진 순열이다. 말의 위치가 $v,ドル 색깔이 $c$일 때, 현철은 식 $E=A[v\oplus H_0(c)]\oplus H_1(c)$을 통해 암호문 $E$를 생성한다. 여기서 $\oplus$는 비트 단위 XOR 연산자이다.

게임을 생성하는 과정에서 말이 각 칸에 위치할 확률은 동일하며, 말의 위치는 서로 독립적이다.

데이터를 모두 암호화한 현철은 암호문이 어느 정도의 정보를 담고 있는지 궁금해졌다. 암호문이 주어질 때, 우영이가 이길 확률을 계산하여 현철에게 알려주도록 하자. 이때 우영이가 이길 확률이란, 주어진 암호문을 생성하는 암호 $H_0,ドル $H_1$과 말의 위치 $v$로 가능한 경우의 수를 $X,ドル 그중 우영이가 이기는 경우의 수를 $Y$라고 할 때, $\frac{Y}{X}$이다.

입력

첫 번째 줄에 노드의 개수를 나타내는 정수 $N$(2ドル\le N\leq 256$), 간선의 개수를 나타내는 정수 $M$(1ドル\leq M\leq 100,円 000$)이 주어진다.

두 번째 줄 부터 $M$개의 줄에 공백으로 구분된 서로 다른 두 정수 $p,ドル $q$(0ドル\leq p,ドル $q\le N-1$)가 주어지며 이는 $p$번 노드에서 $q$번 노드로 가는 간선이 존재한다는 것을 뜻한다. 어떤 $p$와 $q$에 대해서 $p$번 노드와 $q$번 노드를 잇는 동일한 간선이 여러 개 존재할 수도 있다.

다음 줄에는 256ドル$개의 정수 $A[i]$(0ドル\leq A[i]\le 255$)가 순서대로 주어진다.

다음 줄에는 말의 개수를 나타내는 정수 $K$(1ドル\leq K\le 2N$)가 주어진다.

다음 줄부터 $K$개의 줄에 두 정수 $c_i$(0ドル\leq c_i\le N-1$), $E_i$(0ドル \leq E_i \le 255$)가 주어지며 $i$번 말이 색깔이 $c_i$이고 $v_i$번 노드에 놓여 있을 때, $E_i=A[v_i\oplus H_0(c_i)]\oplus H_1(c_i),ドル 0ドル\leq v_i\le N-1$를 만족한다.

주어지는 그래프는 DAG(Directed acyclic graph, 유향 비순환 그래프)이며, $A$는 순열이다. 그리고 주어지는 데이터를 생성할 수 있는 게임이 적어도 하나 이상 존재한다.

출력

첫 번째 줄에 암호화된 데이터가 우영이가 이기는 게임이었을 확률을 10ドル^9+7$로 나눈 나머지를 출력하라. 단, 10ドル^9+7$은 소수이다.

기약분수 $\frac{p}{q}(p\ge 0,q>0,\gcd(p,q) =1)$를 $M$으로 나눈 나머지는 $q^{-1}$가 $q\cdot q^{-1}\equiv 1\pmod M$을 만족하는 정수, 즉 $q$의 $M$에 대한 모듈로 곱셈 역원일 때, $p\cdot q^{-1}\pmod M$로 정의한다. 만약 정수일 경우 $q=q^{-1}=1$이므로 $p\pmod M$를 의미한다.

확률을 10ドル^9+7$로 나눈 나머지가 유일하게 결정되는 입력만 주어진다. 즉, 답은 정수이거나 기약분수로 나타냈을 때 분모가 10ドル^9+7$과 서로소인 경우만 주어진다.

제한

힌트