Stair Numbers

Time limit

Memory limit

128 MB

Problem

Consider the number 45656.

The absolute difference between every pair of adjacent digits in this number is 1. Such a number is called a stair number.

Given a natural number N, count the stair numbers of length N that contain every digit from 0 through 9 at least once. A number cannot start with 0, and a number that starts with 0 is not counted as a stair number.

Input

The first line contains the natural number N.

1 <= N <= 100

Output

Print the number of stair numbers satisfying the condition, modulo 1,000,000,000.

Hint

For reference, the sum of the answers for N = 1 through N = 40 is 126461847755.