No tags yet

No tag edit access

time limit per test: 0.25 sec.

memory limit per test: 4096 KB

memory limit per test: 4096 KB

input: standard

output: standard

output: standard

Let us call P(n) - the product of all digits of number n (in decimal notation).

For example, P(1243)=1*2*4*3=24; P(198501243)=0.

Let us call n to be a good number, if (p(n)<>0) and (n mod P(n)=0).

Let us call n to be a perfect number, if both n and n+1 are good numbers.

You are to write a program, which, given the number K, counts all such

numbers n that n is perfect and n contains exactly K digits in decimal notation.

For example, P(1243)=1*2*4*3=24; P(198501243)=0.

Let us call n to be a good number, if (p(n)<>0) and (n mod P(n)=0).

Let us call n to be a perfect number, if both n and n+1 are good numbers.

You are to write a program, which, given the number K, counts all such

numbers n that n is perfect and n contains exactly K digits in decimal notation.

Only one number K (1<=K<=1000000) is written in input.

Output the total number of perfect k-digit numbers.

Input

1

Output

8

Author: | All-Russian mathematical olympiad jury |

Resource: | District mathematical olympiad, 8th form |

Date: |

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/17/2019 12:03:44 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|