수열 문제이다.

수열 an 은 다음과 같이 정의 된다.

• 0 번째 수가 1
• 1 번째 수가 1
• a_i = 3*a_i-1 - a_i-2 ( i >= 2)

입력

n 이 입력으로 주어진다. 1 <= n <= 2000000000

출력

10^5 으로 나눈 나머지를 출력한다.

입출력 예

입력    3    출력    5  

주기가 37500 이라는데...값을 n 까지 출력해봐도 잘 모르겠네요;;; 조언 좀 구할 수 있을까요.