#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int LEN = 13;
const int fact[10][4] = {
	{0,0,0,0},
	{0,0,0,0},
	{1,0,0,0},
	{0,1,0,0},
	{2,0,0,0},
	{0,0,1,0},
	{1,1,0,0},
	{0,0,0,1},
	{3,0,0,0},
	{0,2,0,0}
};
const int CNT = 14672;
const int mod = 1e9 + 7;
long long n;
int k;
int tot,d[LEN + 5];
int e[4],cnt;
int c[CNT + 5];
long long f[LEN + 5][LEN * 3 + 5][LEN * 2 + 5][LEN + 5][LEN + 5][2];
long long dfs(int x,int c2,int c3,int c5,int c7,int lead,int top)
{
	if(c2 < 0 || c3 < 0 || c5 < 0 || c7 < 0)
		return 0;
	if(!x)
		return !c2 && !c3 && !c5 && !c7;
	if(!top && ~f[x][c2][c3][c5][c7][lead])
		return f[x][c2][c3][c5][c7][lead];
	long long ret = 0;
	int bound = top ? d[x] : 9;
	for(register int i = (lead && x > 1) ? 0 : 1;i <= bound;++i)
		ret += dfs(x - 1,c2 - fact[i][0],c3 - fact[i][1],c5 - fact[i][2],c7 - fact[i][3],lead && !i,top && i == bound);
	!top && (f[x][c2][c3][c5][c7][lead] = ret);
	return ret;
}
void dfs(int i,long long x)
{
	const int d[4] = {2,3,5,7};
	if(x > n)
		return ;
	c[++cnt] = dfs(tot,e[0],e[1],e[2],e[3],1,1);
	for(;i < 4;++i)
		++e[i],dfs(i,x * d[i]),--e[i];
}
struct note
{
	int x,y;
	inline bool operator<(const note &o) const
	{
		return (long long)c[x] * c[y] < (long long)c[o.x] * c[o.y];
	}
};
priority_queue<note> q;
int ans;
int main()
{
	memset(f,-1,sizeof f);
	scanf("%lld%d",&n,&k);
	for(register long long i = n;i;d[++tot] = i % 10,i /= 10);
	dfs(0,1),k = min(k,cnt * cnt),sort(c + 1,c + cnt + 1);
	for(register int i = 1;i <= cnt;++i)
		q.push((note){i,cnt});
	for(note p;k;--k)
		p = q.top(),q.pop(),
		ans = (ans + (long long)c[p.x] * c[p.y]) % mod,
		p.y > 1 && (--p.y,q.push(p),1);
	printf("%d\n",ans);
}