Reversible Numbers

A positive integer n is called reversible if the sum of n and its reversal (that is, the number obtained by writing the digits of n in reverse order) consists entirely of odd digits. Note that neither n nor its reversal may have any leading zeroes. For example,

• 36 + 63 = 99, so 36 and 63 are reversible.
• 409 + 904 = 1313, so 409 and 904 are reversible.

It is known that there are 120 reversible numbers below 10³ (one‐thousand). Given a positive integer exponent x (with 3 ≤ x ≤ 400), count how many reversible numbers are less than or equal to 10^x.

Explanation: A number n (with at least two digits) is reversible if n + reverse(n) has every digit odd. For example, when n = 36 (2 digits) we have 36 + 63 = 99 (both digits odd) and when n = 409 (3 digits) we have 409 + 904 = 1313. Note that numbers ending in 0 are not allowed because their reversal would have a leading zero.

It turns out that a combinatorial analysis (taking account of the carries produced when adding digit‐pairs in the usual algorithm) shows that if we define

then the total number of reversible numbers with d digits is f(d) and the answer to the problem is

For example, when x = 3 the reversible numbers have 2‐ or 3‐digits and their total count is 20 + 100 = 120.

Your task is to compute the answer for a given exponent x (3 ≤ x ≤ 400). Note that the numbers involved can be very huge – you will need to use arbitrary‐precision arithmetic.

inputFormat

The input is a single integer x (3 ≤ x ≤ 400), representing the exponent in 10^x.

outputFormat

Output a single line containing the count of reversible numbers less than or equal to 10^x.

sample

3

120