### 问题描述 "神社の桜、もう３巡目よ？" —— "神社的樱花，已经开了三巡了吗？" 十六夜咲夜给你出了一道题，题目的内容自然也和 $16$ 有关。咲夜给了你一个 $16$ 进制整数 $N$，你需要求出 $1\sim N$ 下有多少个 $16$ 进制数由 $k$ 个不同的数字组成（不含前导 $0$），结果对 $10^9+7$ 取模。 聪明的你能解决这个问题嘛？（如果解决不出来可能会被咲夜用飞刀钉在墙上哦）。 ### 输入格式 输入一行，包含 $2$ 个正整数 $N,k$，这里的 $N$ 是一个大写的 $16$ 进制数字。 ### 输出格式 输出一行，包含一个整数，为 $1\sim N$ 下符合题目要求的数字，结果对 $10^9+7$ 取模。 ### 样例输入1 ```text 1E 2 ``` ### 样例输出1 ```text 14 ``` ### 样例输入2 ```text 1919810 3 ``` ### 样例输出2 ```text 427528 ``` ### 说明 对于样例 $1$，有 $\text{10,12,13,14,15,16,17,18,19,1A,1B,1C,1D,1E}$。 ### 评测数据规模 $1\le N\le 16^{2\times 10^5},1\le k \le 16$。