#include "bits/stdc++.h" #include #define rep(i,n) for(ll i = 0; i < n; i++) typedef long long ll; typedef unsigned long long ull; using namespace std; #define vll vector> #define vl vector #define vi vector #define vii vector> #define pb push_back #define pf push_front #define ld long double #define Sort(a) sort(a.begin(),a.end()) #define cSort(a,cmp) sort(a.begin(),a.end(),cmp) #define reSort(a) sort(a.rbegin(), a.rend()) static const ll llMAX = numeric_limits::max(); static const int intMAX = numeric_limits::max(); static const ll llMIN = numeric_limits::min(); static const int intMIN = numeric_limits::min(); static const ll d_5 = 100000; static const ll d9_7 = 1000000009; static const ll d_9 = 1000000000; static const double PI=3.14159265358979323846; //< void Printvector(std::vector a){ int size = a.size(); rep(i,size){ cout< void Printvector(std::vector> a){ int size = a.size(); rep(i,size){ int size2=a[i].size(); rep(j,size2){ cout< prime_factor(int64_t n) { unordered_map ret; for(int64_t i = 2; i * i <= n; i++) { while(n % i == 0) { ret[i]++; n /= i; } } if(n != 1) ret[n] = 1; return ret; } /*struct datas{ int num; int index; }; bool cmp(const datas &a, const datas &b) { return a.num < b.num; }*/ template vector getaccum(vector a){ int size=a.size(); vector ans(size); ans[0]=a[0]; for(int i=0;iy)swap(x,y); ll ret=0; for(ll i=1;i<=x+1;i++){ ret+=linercomb(i+y,y,d9_7); ret%=d9_7; } return ret; } vl Digit_DP(string s){ ll size=s.size(); int mas=1000; vector> dp(size+1,vll(2,vl(mas,0))); // dp[ 決めた桁数 ][ 未満フラグ ][ 問題に応じての処理 ] := 総数 dp[0][0][0]=1; for(int i=0;i=mas)break;; dp[i+1][j||(d>m>>d; vl n1=Digit_DP(m); vl n2=Digit_DP(d); //Printvector(n1); //Printvector(n2); ll ans=0; rep(i,1000){ ans+=(n1[i]*n2[i])%d9_7; ans%=d9_7; } //cout<