Problem 5C. 幸运数

题目描述

pzr 不喜欢 \(6\)，他认为，所有 不含 \(6\) 的正整数 都是幸运数。

pzr 将所有幸运数（的十进制表示）排成一排，形成一个无限长的字符串 \(s=1234578910111213141517\cdots \)

给定 \(k\)，求 \(s\) 的第 \(k\) 个字符。

输入格式

仅一个正整数 \(k\)。

输出格式

仅一个 \(0\sim 9\) 之间的数位，表示答案。

样例输入1

16

样例输出1

3

样例输入2

123457

样例输出3

9

样例输入3

1000000000000000

样例输出3

5

数据范围及约定

对于 \(60\%\) 的数据，\(1\le k\le 10^6\)

对于所有数据，\(1\le k \le 10^{15}\)