독립 집합

트리 $T = (V, E)$는 사이클이 없는 연결된 무향 단순 그래프이다. 이 문제에서는 각 정점이 $c$개의 색 중 하나로 칠해진 트리를 다룬다. 이런 트리를 색칠된 트리라고 부른다.

두 색칠된 트리 $T_1 = (V_1, E_1)$과 $T_2 = (V_2, E_2)$는 다음 두 조건을 모두 만족하면 같다고 본다.

• 전단사 함수 $\pi : V_1 \to V_2$가 존재하여, 임의의 정점 쌍 $u, v \in V_1$에 대해 $\{u, v\} \in E_1$과 $\{\pi(u), \pi(v)\} \in E_2$가 동치이다.
• 모든 정점 $v \in V_1$에 대해, $T_1$에서 $v$의 색과 $T_2$에서 $\pi(v)$의 색이 같다.

트리 $T = (V, E)$의 독립 집합은 서로 다른 두 정점이 간선으로 연결되어 있지 않은 정점 부분집합 $S \subseteq V$이다. 독립 집합의 크기는 $S$에 속한 정점의 수이다.

정수 $\ell$, $r$, $c$가 주어진다. 최대 독립 집합의 크기가 $\ell$ 이상 $r$ 이하인 서로 다른 $c$색 칠해진 트리는 몇 개인가? 답이 매우 클 수 있으므로 $998244353$으로 나눈 나머지를 구한다.

한 줄에 정수 $\ell$, $r$, $c$가 주어진다. ($1 \le \ell \le r \le 500000$, $1 \le c \le 998244352$)

최대 독립 집합의 크기가 $[\ell, r]$ 구간에 속하는 서로 다른 $c$색 칠해진 트리의 개수를 $998244353$으로 나눈 나머지를 한 줄에 출력한다.

첫 번째 예제의 설명이다. 최대 독립 집합의 크기가 1, 2, 3인 서로 다른 1색 트리는 모두 아래와 같다.