Interesting number

http://acm.timus.ru/problem.aspx?space=1&num=1385

Time Limit: 1.0 second

Memory Limit: 1 000 KB

Tyomitch calls the number with 2N digits (without leading zeroes) "interesting", if it's divisible by both the number formed from its first N digits and the number formed from its last N digits. For example, 1020 is "interesting" (divisible by 10 and 20) and 2005 is not. Tyomitch wants to know how many "interesting" 2N-digit numbers exist. You are to help him.

1. Input

Input contains an integer N (1 ≤ N ≤ 10000).

2. Output

Output the number of "interesting" 2N-digit numbers.

3. Sample Input

1

4. Sample Output

14

5. Hint

11, 12, 15, 22, 24, 33, 36, 44, 48, 55, 66, 77, 88, 99.

Problem Author: Alexander Ipatov

Problem Source: Petrozavodsk summer training camp, August 2005.


timus1385 (2008-02-23 15:37:05由localhost编辑)

ch3n2k.com | Copyright (c) 2004-2020 czk.