Counting Sam Numbers

A Sam Number is defined as a number such that the absolute difference between any two adjacent digits is at most $$2$$, i.e., for every adjacent pair of digits $$d_i$$ and $$d_{i+1}$$, it holds that $$|d_i-d_{i+1}|\le 2$$. A k-digit Sam Number is a Sam Number with exactly k digits, and note that a k-digit number cannot have a leading zero.

Given a positive integer k, count the total number of k-digit Sam Numbers.

inputFormat

The input consists of a single integer k (1 ≤ k ≤ 50, for example) on one line, representing the number of digits.

outputFormat

Output a single integer, which is the number of k-digit Sam Numbers.

sample

1

9