Description
Solution
首先每一位上有(0)就不合法，然后很多不同的排列乘起来是相同的，所以盲猜最后的(f)函数有用的值不多。
经过搜索发现最多只有不到(10000)个。
为啥别的题解都是8282我搜出来是9200？
那就把这些合法的(f)函数值都放进哈希表存起来，然后设(dp_{i, x, 0/1})表示当前(dp)到了第(i)位，乘积为哈希表里的第(x)个状态，有没有卡到最高位。
这个朴素的数位(dp)就枚举一下上一位的乘积，这一位选什么数即可。
注意要考虑前导零的情况。
然后我们就搜出来每种合法状态有多少个数会变成它，那么对于一个合法的位置((i, j))，它上面就有(tot_i imes tot_j)个金矿。
那么对(tot)排序，将一个二元组((i, j))放进堆里表示这是(tot)数组的第(i)个和第(j)个数相乘。
((i, j))可以转移到((i + 1, j))和((i, j + 1))，但是这样直接转移会有一个小问题，((i - 1, j))和((i, j - 1))都能转移到((i, j))，所以再记录一下上一次是不是将(j)加一，如果上次将(j)加一，那么这次不能再将(i)加一。
这样堆中的状态变为了一个三元组((i, j, p))，代表(tot)数组的第(i)个和第(j)个数相乘，上次是不是将(j)加一。
Code
/*
_______ ________ _______
/ _____ / ______ / _____
/ / \_ _ __ _ / / _ __ _ / / \_
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | __ | | | | | | | | | |
| | __ | | / / | | | | | | / / | | __
\_____/ / / / / / \_____ / / / / / \_____/ /
\_______/ \___/ \___/ \______/\__ \___/ \___/ \_______/
*/
#include <iostream>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define ll long long
#define RE register
const int HashMOD = 100077;
const int MOD = 1e9 + 7;
int k, head[HashMOD + 5], num, fa[20], shu[20], len, tot[10005], ans;
ll dp[14][10005][2];
ll n;
struct Node {
int next;
ll to;
} edge[HashMOD + 5];
struct HeapNode {
int pos1, pos2;
ll qz;
bool flag;
bool operator < (const HeapNode &rhs) const {
return qz < rhs.qz;
}
};
inline void Add(ll x) {
int pos = x % HashMOD;
for (RE int i = head[pos]; i; i = edge[i].next) {
ll v = edge[i].to;
if (v == x) return;
}
edge[++num] = (Node){head[pos], x};
head[pos] = num;
return;
}
inline int Find(ll x) {
int pos = x % HashMOD;
for (RE int i = head[pos]; i; i = edge[i].next) {
ll v = edge[i].to;
if (v == x) return i;
}
return 0;
}
inline ll Ksm(ll a, int b) {
ll tmp = 1;
while (b) {
if (b & 1) tmp = tmp * a;
a = a * a;
b >>= 1;
}
return tmp;
}
void Work() {
ll tmp = 1;
for (RE ll i = 1; i <= 9; i++)
tmp *= Ksm(i, fa[i]);
Add(tmp);
return;
}
void Dfs(int x, int sum) {
if (x == 10 || sum == 12) {
Work();
return;
}
for (RE int i = 0; i <= 12 - sum; i++)
fa[x] = i, Dfs(x + 1, sum + i);
return;
}
void Solve(ll n) {
ll tmp = n;
while (n) {
shu[++len] = n % 10;
n /= 10;
}
for (RE int i = 1; i <= shu[len]; i++) dp[len][Find(i)][i == shu[len]] = 1;
for (RE int i = len - 1; i >= 1; i--) {
for (RE int now = 1; now <= 9; now++)
dp[i][Find(now)][0]++;
for (RE int lst = 1; lst <= num; lst++)
for (RE int p = 0; p <= 1; p++)
if (dp[i + 1][lst][p]) {
for (RE int now = 1; now <= (p ? shu[i] : 9); now++) {
ll ne = edge[lst].to * now;
dp[i][Find(ne)][p && (now == shu[i])] += dp[i + 1][lst][p];
}
}
}
for (RE int i = 1; i <= num; i++)
if (edge[i].to <= tmp)
tot[i] += dp[1][i][0] + dp[1][i][1];
return;
}
bool Cmp(int a, int b) {
return a > b;
}
void Qm(int &x) {
x -= MOD;
x += x >> 31 & MOD;
return;
}
void Calc(int k) {
sort(tot + 1, tot + num + 1, Cmp);
priority_queue<HeapNode> q;
q.push((HeapNode){1, 1, 1LL * tot[1] * tot[1] % MOD, false});
while (!q.empty() && k) {
HeapNode tmp = q.top(); q.pop();
int pos1 = tmp.pos1, pos2 = tmp.pos2;
if (!tmp.qz) break;
k--;
Qm(ans += tmp.qz % MOD);
if (pos1 <= num && tmp.flag == false) q.push((HeapNode){pos1 + 1, pos2, 1LL * tot[pos1 + 1] * tot[pos2], false});
if (pos2 <= num) q.push((HeapNode){pos1, pos2 + 1, 1LL * tot[pos1] * tot[pos2 + 1], true});
}
return;
}
int main() {
Dfs(1, 0);
scanf("%lld%d", &n, &k);
Solve(n);
Calc(k);
printf("%d", ans);
return 0;
}