오각형 점 세기

오각형 모양을 단계별로 확장하며 변 위에 점을 찍는다. 1단계에는 점이 5개 있다. 2단계부터는 직전 단계보다 새 점이 3N + 1개 더 생긴다. 즉, 2단계에서는 7개, 3단계에서는 10개가 추가된다.

정수 N이 주어졌을 때, N단계의 점 개수를 구하라.

첫째 줄에 정수 N이 주어진다.

1 <= N <= 10,000,000

N단계의 점 개수를 45678로 나눈 나머지를 출력한다.