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

USU Internal Contest March'2002

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Sum of Digits of the Sum of Numbers

Time limit: 1.0 second
Memory limit: 64 MB
Let us denote the sum of digits of the number N by S(N). In this problem, we want you to determine, how often the following equality holds:
S(A + B) = S(A) + S(B)

Input

The input contains a single integer K, 2 ≤ K ≤ 50.

Output

You should output the number of pairs of K-digit numbers A and B to satisfy the above equality. Counting that number you should be aware of the following:
  1. numbers A and B should not have leading zeroes;
  2. while counting the total number of pairs, the order of numbers A and B matters, thus, for instance, (12, 26) and (26, 12) are different pairs that satisfy the conditions of the problem.

Sample

inputoutput
2
1980
Problem Author: Leonid Volkov
Problem Source: USU Internal Contest, March 2002
To submit the solution for this problem go to the Problem set: 1206. Sum of Digits of the Sum of Numbers