Salary
Time limit1sMemory limit1024 MB
Concatenate 1^3, 2^3, 3^3, ... as decimal digits and report the k-th digit of the resulting string.
- Level
Medium4 of 10
- Topics
- Math, Implementation, String, Brute force
- Solved
- No attempts yet
Problem
Miroslav recently started a job. Because he is a very valuable employee, his salary grows not by days but by hours. More precisely, each month he receives as many leva as the cube of the number of the month he has worked (not the calendar month). So in the first month he receives 1 lev, in the second 8 leva, in the third 27 leva, and so on.
As everyone knows, tax laws are a difficult thing. In the country where Miroslav works, a new law was passed. Its essence lies in the fact that the percentage of tax paid by the employee is computed by the following formula:
- Write down the employee's salary for the first month, then to its right write his salary for the second month, and so on, until the number of digits in the written number becomes greater than k.
- The k-th digit of the resulting number is the sought tax percentage. A separate k was introduced for each company. Miroslav knows this number for the company where he works. Now he wants to find out what percentage of his salary he will pay as tax.
Write a program salary that finds what percentage Miroslav's tax is.
Input
The first line of the standard input contains a single integer k.
Output
On a single line of the standard output the program must print a single integer x, the sought percentage.
Constraints
- 1 ≤ k ≤ 1 000 000
- 0 ≤ x ≤ 9
Hint
When computing the tax in the second example, the string 182764125 is obtained. The seventh digit is 1.