题目背景

iL(imaginary Lies)虚构的谎言：

有人冒险道出了真相，

却被认定是谎言，

有人明明说的是谎言，

却因为美丽而被追捧为真相。

——佚名

如果说一个人的欺骗程度与其所处的环境和自身有关，

那么一个数字的谎言值就与它的进制与大小有关。

如果都看不破数字的谎言，那又如何看透人的虚假呢？

题目描述

定义正整数\(x\)的谎言值\(f(x)\)为\(x\)在\(a\)进制下各个数位上的数的最大值,求：

\[\sum_{i=1}^{a^n}{f(i)}\]

输入格式

一行两个整数\(n,a\)

输出格式

结果在十进制下对\(10^9+7\)取模的结果

样例

input#1:
2 4
output#1:
35

input#2:
15 1773
output#2:
614902424

说明与数据范围

样例1解释

这里给出\(f(9)\)的计算过程：

\((9)_{10}=(21)_{4}\)

\(f(9)=\max(2,1)=2\)

\(\sum_{i=1}^{4^2}{f(i)}=1+2+3+1+1+2+3+2+2+2+3+3+3+3+3+1=35\)

数据范围

\(5\%\)的数据满足\(a\leq 8,n\leq 8\);

\(30\%\)的数据满足\(n\leq 2\times 10^6,a\leq 2\times 10^5\)；

其中有\(5\%\)的数据满足\(a=10,n\leq 7\);

另有\(20\%\)的数据满足\(n\leq 3\);

\(100\%\)的数据满足

\(0\leq n\leq 2\times 10^6,2\leq a\leq 10^9,\forall i\neq j, n_i\neq n_j\)

本题时空限制：1000ms/128MB

来源： HGV&STOJ NOI Online 考前热身赛 T4