// problem #78
계단 수
시간 제한 2.0초
인접한 자리의 차이가 1인 수를 계단 수라 한다(0으로 시작 안 함). 길이 N인 계단 수의 개수를 1,000,000,000으로 나눈 나머지를 구하시오.
입력
첫 줄에 자리수 N.
출력
계단 수 개수 mod 1,000,000,000.
제한
- 1 ≤ N ≤ 100
예제
입력 1
1
출력 1
9
입력 2
2
출력 2
17
// problem #78
인접한 자리의 차이가 1인 수를 계단 수라 한다(0으로 시작 안 함). 길이 N인 계단 수의 개수를 1,000,000,000으로 나눈 나머지를 구하시오.
첫 줄에 자리수 N.
계단 수 개수 mod 1,000,000,000.
1
9
2
17