Sky Full of Stars

태양계의 행성 중 하나인 Atmosphere University에서는 많은 학생이 빙고 게임을 좋아한다.

이 행성의 한 달은 $n^2$일로 이루어진다는 것은 잘 알려져 있으므로, n행 n열의 정사각 행렬로 표현되는 달력이 매우 인기가 있다.

기상 조건은 더욱 특이하다. 대기의 독특한 구성 성분이 햇빛과 상호 작용하기 때문에, 하늘은 매일 파란색, 초록색, 빨간색의 세 가지 색 중 하나를 띤다.

빙고를 하려면 한 달 동안 하늘을 관찰해야 한다. 매일이 지나면 그날에 해당하는 칸을 그날 하늘의 색, 즉 파란색, 초록색 또는 빨간색으로 칠한다.

달이 끝나면 학생들은 달력을 살펴본다. 적어도 하나의 행 또는 열이 한 가지 색의 칸으로만 이루어져 있다면, 그 달을 행운의 달이라고 한다.

적어도 하나의 칸에서 색이 다르면 달력의 두 색칠이 서로 다르다고 하자. 서로 다른 색칠은 3^{n ⋅ n}개임을 쉽게 알 수 있다. 이 중 행운의 색칠은 몇 개인가? 이 수는 매우 클 수 있으므로, 998244353으로 나눈 나머지를 출력한다.

입력의 첫 번째이자 유일한 줄에 달력의 행과 열의 수를 나타내는 하나의 정수 n (1 ≤ n ≤ 1000 000)이 주어진다.

달력의 행운의 색칠 수를 998244353으로 나눈 나머지를 출력한다.

첫 번째 예제에서는 유일한 열이 한 가지 색의 칸으로만 이루어져 있으므로 어떤 색칠이든 행운의 색칠이다.

두 번째 예제에는 행운의 색칠이 많이 있으며, 특히 다음 색칠들은 행운의 색칠이다.

반면 다음 색칠들은 행운의 색칠이 아니다.