Number of Binominal Coefficients

题意翻译

给定质数 $p$ 和整数 $\alpha,A$,求满足 $0 \le k \le n \le A$ 且 $p^{\alpha}|\binom nk$ 的数对 $(n,k)$ 的个数。 $p,\alpha \le 10^9$,$A < 10^{1000}$,答案对 $10^9+7$ 取模。

题目描述

For a given prime integer $ p $ and integers $ α,A $ calculate the number of pairs of integers $ (n,k) $ , such that $ 0<=k<=n<=A $ and ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF582D/d96ba5d6be086c3d0df101778af0c927c054edb9.png) is divisible by $ p^{α} $ . As the answer can be rather large, print the remainder of the answer moduly $ 10^{9}+7 $ . Let us remind you that ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF582D/d96ba5d6be086c3d0df101778af0c927c054edb9.png) is the number of ways $ k $ objects can be chosen from the set of $ n $ objects.

输入输出格式

输入格式


The first line contains two integers, $ p $ and $ α $ ( $ 1<=p,α<=10^{9} $ , $ p $ is prime). The second line contains the decimal record of integer $ A $ ( $ 0<=A&lt;10^{1000} $ ) without leading zeroes.

输出格式


In the single line print the answer to the problem.

输入输出样例

输入样例 #1

2 2
7

输出样例 #1

3

输入样例 #2

3 1
9

输出样例 #2

17

输入样例 #3

3 3
9

输出样例 #3

0

输入样例 #4

2 4
5000

输出样例 #4

8576851

说明

In the first sample three binominal coefficients divisible by 4 are ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF582D/bed998b9151c636dcb106a9d59d333dcf36e51ee.png), ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF582D/ea939f10119dfab9c0d926b557f9bc915ee93a82.png) and ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF582D/7af37d32634caf541e32a8e83877ecf38ed8d42f.png).