33913번 - even 하게 익은 SCON

문제

SCON과 SCCC를 바라보던 문성이는 흥미로운 규칙을 발견했다! 바로 두 문자열에서 문자 ‘S’와 ‘C’의 개수를 합하면 항상 짝수가 된다는 것이다. 이를 본 문성이는 문득 알파벳 대문자로 구성된 길이가 $N$인 문자열 중에서 ‘S’와 ‘C’의 개수의 합이 짝수인 문자열이 몇 개나 될지 궁금해졌다.

문성이의 궁금증을 해결해 주자!

입력

첫째 줄에 문자열의 길이를 의미하는 정수 $N$이 주어진다.

출력

알파벳 대문자로 구성된 길이가 $N$인 문자열 중 ‘S’, ‘C’의 개수의 합이 짝수인 문자열의 개수를 1ドル,円 000,円 000,円 007(=10^9+7)$로 나눈 나머지를 출력하라.

제한

• 1ドル\le N\le 1,円 000,円 000$
• 입력으로 주어지는 수는 모두 정수이다.

힌트