34260번 - 서브태스크 점수 서브태스크

문제

LGCPC 대회 문제를 준비하는 디오스(DIOS)는 맞힌 서브태스크(subtask, 부분 문제)의 집합이 다르지만 최종 점수가 같은 참가자들이 얼마나 많이 나올지 궁금해졌다.

대회는 $P$개의 문제로 구성되어 있다. 각 문제는 1개 이상의 서브태스크로 구성되어 있는데, $i$번 문제는 $N_i$개의 서브태스크로 구성되어 있고, $i$번 문제의 $j$번 서브태스크의 점수는 $S_{i,j}$점이다. 참가자의 최종 점수는 $P$개의 문제에서 맞힌 서브태스크들의 점수의 합이다. 각 문제의 서브태스크 점수의 합은 정확히 100점이다.

서브태스크는 위계 관계를 가질 수 있다. 위계를 나타내는 쌍 $(x, y)$는 $y$번 서브태스크를 맞히기 위해서는 $x$번 서브태스크도 맞혀야 함을 의미한다. 위계는 전이적으로 적용된다. 즉, 위계가 $(x, y),ドル $(y, z)$와 같이 있다면, $z$번 서브태스크를 맞히기 위해서 $x, y$번 서브태스크를 모두 맞혀야 한다. 위계 관계는 한 문제 안에서만 존재하며, 서로 다른 문제의 서브태스크들 사이에는 어떠한 제약도 없다.

참가자의 최종 점수가 정확히 $t$점이 되도록 문제들의 서브태스크를 고르는 방법의 수를 $R_t$라고 하자. 여기에서 "방법"은 각 문제마다 선택한 서브태스크들의 집합을 의미하며, 선택한 서브태스크들은 위계 관계를 만족해야 한다. 서브태스크를 하나도 선택하지 않는 것도 유효한 방법이므로 $R_0 \ge 1$임에 유의하라.

$R_0, R_1, \cdots, R_{100\times P}$를 구하는 프로그램을 작성하라.

입력

첫째 줄에 문제의 개수 $P$가 주어진다.

이후 문제 $P$개의 정보가 다음과 같은 형식으로 차례대로 주어진다:

첫째 줄에 서브태스크의 개수 $N_i$와 서브태스크 위계의 수 $M_i$가 공백으로 구분되어 주어진다.

둘째 줄에 각 서브태스크의 점수 $S_{i,1}, S_{i,2}, \cdots, S_{i, N_i}$가 공백으로 구분되어 주어진다. 이는 $i$번 문제의 $j$번 서브태스크를 맞히면 $S_{i,j}$점을 얻는다는 것을 의미한다.

다음 $M_i$개의 줄에 서브태스크의 위계를 나타내는 두 정수 $X_{i,k}$와 $Y_{i,k}$가 공백으로 구분되어 주어진다. 이는 $i$번째 문제의 $Y_{i,k}$번 서브태스크를 맞히기 위해서는 $X_{i,k}$번 서브태스크 또한 맞혀야 함을 의미한다.

출력

출력해야 하는 수의 개수와 크기가 매우 커질 수 있으므로, $\sum_{t=0}^{100\times P} R_t \times t$를 998ドル,244円,353円$으로 나눈 나머지를 출력한다.

제한

• 1ドル \le P \le 30$
• 1ドル \le N_i \le 10$ (1ドル \le i \le P$)
• 0ドル \le M_i \le N_i(N_i-1)/2$ (1ドル \le i \le P$)
• 1ドル \le S_{i,j} \le 100$ (1ドル \le i \le P$; 1ドル \le j \le N_i$)
• $\sum_{j=1}^{N_i} S_{i,j} = 100$ (1ドル \le i \le P$)
• 1ドル \le X_{i,k} < Y_{i,k} \le N_i$ (1ドル \le i \le P$; 1ドル \le k \le M_i$)
• 중복된 위계 관계는 주어지지 않는다.
• 전이적으로 유도될 수 있는 위계 관계가 입력으로 주어질 수 있다.
• 입력으로 주어지는 수는 모두 정수다.

서브태스크

힌트