소 P는 양의 정수 $k$와 막대사탕을 좋아합니다. 소 P는 단순 무향 그래프가 막대사탕 그래프일 필요충분조건을 다음과 같이 정의합니다.
- 모든 정점 $i$에 대하여, $|\lfloor\frac{i}{k}\rfloor-\lfloor\frac{j}{k}\rfloor|>1$을 만족하면서 $i$와 $j$ 사이에 간선이 존재하는 정점 $j$는 존재하지 않습니다.
- 모든 정점 $i$에 대하여, $\lfloor\frac{j}{k}\rfloor-\lfloor\frac{i}{k}\rfloor=1$을 만족하면서 $i$와 $j$ 사이에 간선이 존재하는 정점 $j$는 최대 두 개입니다.
모든 정점은 $0$부터 번호가 매겨집니다.
소 P는 $n$개의 정점을 가진 막대사탕 단순 무향 그래프를 소 W에게 선물로 주었습니다. 그러나 전송 과정에서 우주 방사선이 이 무향 그래프에 영향을 주었습니다. 구체적으로, 각 간선은 일정 확률로 끊어질 수 있습니다.
소 W는 막대사탕 단순 무향 그래프를 받은 후, 그 '막대사탕 정도'를 $\prod_{i=0}^{n-1}(deg_i+t)$로 정의했습니다.
소 P는 소 W가 자신의 막대사탕 그래프를 얼마나 막대사탕답다고 생각할지 알고 싶어 합니다. 하지만 그는 각 간선이 끊어질 확률만 알고 있기 때문에, 그래프가 소 W에게 전달된 후 막대사탕 정도의 기댓값을 계산하기로 했습니다. 소 P는 소수와 큰 수를 좋아하지 않으므로(여기서 소수와 큰수는 반의어가 아닙니다!), 막대사탕 정도의 기댓값을 $998244353$으로 나눈 나머지를 구해야 합니다.
코드의 상수 시간에 유의하십시오.
입력 형식
첫 번째 줄에 다섯 개의 정수 $n, m, k, t, sub$가 주어지며, $sub$는 서브태스크 번호입니다.
다음 $m$개의 줄에는 각각 세 개의 정수 $u_i, v_i, p_i$가 주어지며, 이는 $u_i$와 $v_i$ 사이에 무향 간선이 존재하고 우주 방사선에 의해 끊어질 확률이 $p_i$임을 의미합니다.
출력 형식
기댓값을 $998244353$으로 나눈 나머지를 한 줄에 출력합니다.
예제
입력 1
3 2 3 0 0 0 1 499122177 1 2 499122177
출력 1
499122177
입력 2
4 4 2 1 0 0 1 3 0 2 4 1 3 5 2 3 6
출력 2
998243917
입력 3
6 12 3 114514 0 0 1 1 0 2 9 1 2 2 0 3 6 0 4 8 1 4 17 1 5 1 2 5 9 2 3 5 3 4 3 4 5 6 3 5 15
출력 3
446947426
데이터 범위
| 서브태스크 번호 | 점수 | 추가 제한 |
|---|---|---|
| 1 | 31 | $n\leq19$ |
| 2 | 13 | $k\leq10$ |
| 3 | 13 | $k\leq14$ |
| 4 | 13 | 모든 정점 $i$에 대하여, $\lfloor\frac{j}{k}\rfloor-\lfloor\frac{i}{k}\rfloor=-1$을 만족하면서 $i$와 $j$ 사이에 간선이 존재하는 정점 $j$는 최대 한 개 |
| 5 | 13 | 모든 정점 $i$에 대하여, $\lfloor\frac{j}{k}\rfloor-\lfloor\frac{i}{k}\rfloor=-1$을 만족하면서 $i$와 $j$ 사이에 간선이 존재하는 정점 $j$는 최대 두 개 |
| 6 | 17 | 없음 |
모든 데이터에 대하여: $2\leq k\leq 19$, $k\leq n\leq100$, $m\leq 500$, $0\leq t<10^8$, $p$는 $\bmod\ 998244353$으로 주어짐, $0\leq u_i, v_i\leq n-1$, $u_i\neq v_i$. 주어진 그래프는 막대사탕 그래프입니다.