프로그램 명: ndynamic
제한시간: 1 초

다음 문제의 점화식은 다음과 같다.

n 이 주어질 때 을 구하는 것이 문제이다.

입력

n 이 주어진다.(0 <= n <= 10^15)

출력

을 출력한다. 단 , 값이 클 수 있으므로 10 억 9 로 나눈 나머지를 출력한다.

입출력 예

입력

3

출력

729

입력

5229

출력

964617130

출처:Fate
[질/답] [제출 현황] [푼 후(1)]
[ 채 점 ] [홈으로]  [뒤 로]