#3458. Luck

内存限制:256 MiB 时间限制:10 Sec

题目描述

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

输入格式

 
  第一行一个数k。
  第二行一个数n。

输出格式

  一个数,如题所述。

样例

样例输入


			
1
100

样例输出


			
36

数据范围与提示



  设t为n的位数

  100%的数据1<=k<=t<=106