ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1044. Lucky Tickets. Easy!

Time limit: 2.0 second
Memory limit: 64 MB
The public transport administration of Ekaterinburg is anxious about the fact that passengers don’t like to pay for passage doing their best to avoid the fee. All the measures that had been taken (hard currency premiums for all of the chiefs, increase in conductors’ salaries, reduction of number of buses) were in vain. An advisor especially invited from the Ural State University says that personally he doesn’t buy tickets because he rarely comes across the lucky ones (a ticket is lucky if the sum of its first half of digits is equal to the sum of the second half of digits). So, the way out is found — of course, tickets must be numbered in sequence, but the number of digits on a ticket may be changed. Say, if there were only two digits, there would have been ten lucky tickets (with numbers 00, 11, 22, 33, 44, 55, 66, 77, 88, 99). Maybe under the circumstances the ratio of the lucky tickets to the common ones is greater? And what if we take four digits? A huge work has brought the long-awaited result: in this case there will be 670 lucky tickets. But what to do if there are six or more digits?
So you are to save public transport of our city. Write a program that determines a number of lucky tickets for the given number of digits N.

Input

The only line contains an even integer N that is a number of digits in a ticket (2 ≤ N ≤ 8).

Output

Output a number of tickets such that the sum of the first half of digits is equal to the sum of the second half of digits.

Samples

inputoutput
4
670
2
10
Problem Author: Stanislav Vasilyev
Problem Source: Ural State University Internal Contest October'2000 Students Session