题目名称：墙上的数字 (Wall Number / Ѕиден број)

版权信息： 本题目由马其顿计算机协会（Здружение на информатичарите на Македонија, ZIM）发布。

题目描述

有人在墙上写了一个三位数字。

1. 菲斯尼克（Fisnik） 走了过来，在原数字右侧写下了这三个数字之和的个位数（例如：如果原数字是 175，由于 $1+7+5=13$，他在右侧写下 3，数字变为 1753）。
2. 萨拉（Sara） 走了过来，在右侧写下了当前数字中最后三位数字之和的个位数（如果当前是 1753，最后三位是 7, 5, 3，和为 15，她写下 5，数字变为 17535）。
3. 随后，学校里的其他学生依次排队：每个人都观察当前数字的最后三位，计算它们的和，并将和的个位数写在末尾。

幸运的是，这面墙足够长，可以容纳所有的数字。 给定初始的三位数字，你的任务是输出整个数列中第 $N$ 个位置的数字（从 1 开始计数）。

输入格式

• 第一行：一个三位整数（初始数字）。
• 第二行：一个整数 $N$ ($1 \le N \le 10^{18}$)，表示请求出的数字位置。

输出格式

• 输出该位置上的数字。

限制条件

• 时间限制： 100 毫秒（非常严格，要求高效算法）
• 内存限制： 64 MB
• 分值分布：
  • 20% 的数据：$N \le 10$
  • 60% 的数据：$N \le 100,000$
  • 100% 的数据：$N \le 10^{18}$

样例

样例 1

• 输入：

  175
  5
  

• 输出： 5
• 解释： 数列变化为 1, 7, 5, 3, 5... 第 5 位是 5。

样例 2

• 输入：

  175
  99999
  

• 输出： 9

样例 3

• 输入：

  175
  699265421106171856
  

• 输出： 1