The number is called palindrome if it reads the same from both side. For example 10201 is a palindromic number, 10531 is not. You are given a number n. Your task is to calculate the amount of palindrome positive numbers containing at most n digits and without leading zeroes. This number may be enough large, so you should calculate it modulo 1000000007(10⁹+7).

Input

The input contains single integer number n (1 ≤ n ≤ 100).

Output

Output one number – the answer to the problem.

Samples