Lemon Tree 2

Lemon Tree는 매일 밤 매우 빠르게 성장한다. 그날 존재하는 모든 정점에 대해 다음 과정이 동시에 일어난다.

정점 $v$에 $i$번 종류의 레몬이 열려 있다고 하자.

• 첫째 날의 트리 $T$와 동일한 새로운 트리 하나를 만든다.
• 새 트리의 $i$번 정점이 기존 정점 $v$가 되도록 새 트리를 붙인다.
• 새 트리의 $j$번 정점에는 $j$번 종류의 레몬이 열린다. 단, 기존 정점 $v$에는 그대로 $i$번 종류의 레몬이 열린다.

즉, 각 정점에는 그 정점에 열린 레몬의 종류에 해당하는 정점을 연결점으로 하여 첫째 날의 Lemon Tree 한 그루가 새롭게 자라난다.

따라서 $d$일 차의 Lemon Tree에는 정확히 $N^d$개의 정점이 존재하며, 각 정점에는 레몬이 하나씩 열려 있으므로 레몬 역시 $N^d$개 존재한다.

Lemon Tree를 기른 지 $K$일째가 된 유담이는 다음 값이 궁금해졌다.

• $K$일 차 Lemon Tree에 열린 서로 다른 두 레몬을 고르는 모든 경우에 대해, 두 레몬 사이의 거리의 합

두 레몬 사이의 거리는 두 레몬이 열린 정점 사이의 거리이며, 두 정점 사이의 거리는 두 정점을 잇는 단순 경로에 포함된 간선의 개수이다. 위 값을 구하여라. 답이 매우 클 수 있으므로 $998\,244\,353$으로 나눈 나머지를 출력한다. 단, $998\,244\,353$은 소수이다.