题目描述

考虑一个无限数字串。例如，$\sqrt{47}=6.855654600401\ldots$，去掉小数点后得到无限数字串

6855654600401044124935871449...

现在对这个无限文本执行如下无限过程。按素数从小到大的顺序依次处理 $2,3,5,7,11,\ldots$。处理当前素数 $p$ 时，在当前文本中寻找十进制字符串 p 的第一次出现；如果存在，就把这次出现所覆盖的所有字符替换为空格；如果不存在，则什么也不做。空格会一直保留，并且会阻断后续的子串匹配。例如 1234 789 中不存在字符串 47。

无限过程结束后，文本被空格分成若干数字串。把每个数字串解释成非负整数（允许有前导零），就得到一个整数序列。

给定非完全平方数 $X$ 和下标 $N$，从 $\sqrt X$ 的十进制展开去掉小数点后得到初始无限数字串。求最终序列中下标为 $N$（从 $0$ 开始）的元素，并对 $10^9+7$ 取模。

输入格式

一行包含两个整数 $X,N$。

• $1\le X\le10000$；
• $X$ 不是完全平方数；
• $0\le N\le30$。

输出格式

输出一个整数，表示答案对 $10^9+7$ 取模后的结果。

样例 1

输入

47 1

输出

5654600

样例 2

输入

47 2

输出

4

样例 3

输入

5 10

输出

270897077

说明

样例 2 中对应的最终数字串实际上是 04，转换成整数后为 $4$。