#P3458. Luck

    ID: 2658 传统题 1000ms 512MiB 尝试: 18 已通过: 12 难度: 7 上传者: 标签>CF2300提高+/省选-数位 DP计数 DP一维前缀和补集计数对称性分析

Luck

题目描述

SS 国是一个爱好数字的国度,总有些人会夜以继日的数着数字以占卜凶吉,凡是数字在十进制表示之下有连续 kk 个 44 或 kk 个 77 相连则被认为是幸运的。他们看遍了 11 到 nn 之间的所有数,想考一考你。因为他们预先知道答案,所以他们只需你告诉他们幸运的数字  mod 109+7\bmod 10^{9}+7 就行。

输入格式

第一行一个整数 kk;

第二行一个整数 nn。

输出格式

一个数,表示答案。

1
100
36

数据范围

设 tt 为 nn 的位数 对于 100%100\% 的数据1≤k≤t≤1061\leq k\leq t\leq 10^6