题目描述

今天是你一位金星朋友的生日。你不记得他的准确年龄，但你确定他的年龄不超过 $10^{18}$ 岁。

你打算送给他一个十进制整数作为生日礼物。这个整数不能有前导零，并且它的位数必须等于他的年龄。为了让这个数更有趣，你还要求这个数中任意相邻两位数字不能相同。

他的具体出生日期可以用一个 $0$ 到 $224$ 之间的整数表示（因为金星一年有 $225$ 天）。为了让礼物更有纪念意义，你希望送出的整数除以 $225$ 后的余数恰好等于他的出生日期。

可能满足条件的礼物非常多，你也可以选择送不止一个。请计算满足条件的整数个数，并对 $10^9+7$ 取模。

输入格式

输入一行两个整数 $a,b$：

• $1 \le a \le 10^{18}$，表示朋友的年龄，也就是整数的位数；
• $0 \le b < 225$，表示朋友的出生日期，也就是要求的模 $225$ 余数。

输出格式

输出一个整数，表示满足条件的整数个数，对 $10^9+7$ 取模。

样例 #1

输入

12345 200

输出

323756255

样例 #2

输入

100 87

输出

896364174

样例 #3

输入

100 35

输出

785970618

样例 #4

输入

5000 5

输出

176058968

样例 #5

输入

888888 88

输出

906317283

样例 #6

输入

9999999 99

输出

133442170

样例 #7

输入

101010101010 127

输出

893501348

数据范围

$$1 \le a \le 10^{18},\qquad 0 \le b < 225.$$