这是你金星朋友的生日。你不记得他们确切的年龄，但你确定它不超过 $10^{18}$ 岁。你将送给他们一个十进制数字（无前导零）作为生日礼物。你希望这个数字的位数等于他们的年龄。为了让这个数字更有趣，你要确保没有相邻的两位数字是相同的。

他们确切的出生日期表示为 $0$ 到 $224$ 之间的一个整数（因为金星一年有 $225$ 天）。为了让礼物更具个性，你希望所给出的数字除以 $225$ 的余数与他们的出生日期相同。

你可能有很多种礼物可以选择。你可能决定送出不止一份礼物。请计算出可能的礼物数量，结果对 $10^9 + 7$ 取模。

输入格式

输入包含一行，包含两个空格分隔的整数 $a$ ($1 \le a \le 10^{18}$) 和 $b$ ($0 \le b < 225$)，其中 $a$ 是你朋友的年龄，$b$ 是你朋友的出生日期。

输出格式

输出一个整数，表示你可以给出的有趣的个性化数字的数量。由于这个数字可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

12345 200

样例输出 1

323756255

样例输入 2

100 87

样例输出 2

896364174

样例输入 3

100 35

样例输出 3

785970618

样例输入 4

5000 5

样例输出 4

176058968

样例输入 5

888888 88

样例输出 5

906317283

样例输入 6

9999999 99

样例输出 6

133442170

样例输入 7

101010101010 127

样例输出 7

893501348