Yo`nalishlar
Hozirda online

Statistika

Masalalar soni: 909

Foydalanuvchilar soni: 8819

Jo'natishlar soni: 714352

Muhokama yozuvlari: 4541

Yangiliklar soni: 97

Yangiliklar izohlari: 1174


So'ngi izohlar

777. Palindrome numbers
Vaqt limiti: 1 sekund
Xotira limiti: 64 MB

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(109+7).

Input

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

Output

Output one number – the answer to the problem.

Samples

Input

Output

1

1

9

2

2

18

3

3

108

 

Tayyorladi: Azat Yusupov
Mening urinishlarim(0) Muhokama (30) Jo'natish Eng yaxshi yechimlar Barcha muvaffaqiyatli urinishlar(114) Barcha urinishlar(275)