이웃한 모든 자리의 숫자 차이가 정확히 1인 수를 생각하자. 예컨대 45656은 4와 5, 5와 6, 6과 5, 5와 6이 전부 1씩 차이 나므로 이런 수에 해당한다.

길이가 N인(즉 N자리인) 이러한 수가 모두 몇 개인지 구하라. 단, 0으로 시작하는 수는 세지 않는다.

입력

첫째 줄에 N이 주어진다. N은 1 이상 100 이하의 자연수이다.

출력

조건을 만족하는 수의 개수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다.

예제 입력 1

1

예제 출력 1

9

예제 입력 2

2

예제 출력 2

17