계단 수

45656을 생각해 보자.

이 수는 서로 이웃한 두 자리 숫자의 차이가 모두 1이다. 이런 수를 계단 수라고 한다.

자연수 N이 주어진다. 길이가 N이고 0부터 9까지 모든 숫자가 적어도 한 번씩 등장하는 계단 수의 개수를 구하시오. 수는 0으로 시작할 수 없으며, 0으로 시작하는 경우는 계단 수로 세지 않는다.

첫째 줄에 자연수 N이 주어진다.

1 <= N <= 100

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

참고로 N = 1부터 N = 40까지의 정답을 모두 더하면 126461847755이다.