#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define rep(i,n) for(int i=0; i<(n); i++) #define FOR(i,x,n) for(int i=x; i<(n); i++) #define vint(a,n) vint a(n); rep(i, n) cin >> a[i]; #define vll(a,n) vll a(n); rep(i, n) cin >> a[i]; #define ALL(n) begin(n),end(n) #define RALL(n) rbegin(n),rend(n) #define MOD (1000000007) // #define MOD (998244353) #define INF (1e9+7) #define INFL (2e18) typedef long long ll; typedef unsigned int ui; typedef unsigned long long ull; using vint=vector; using vll=vector; using vbool=vector; using P=pair; templateusing arr=vector>; templateint popcount(T &a){int c=0; rep(i, 8*(int)sizeof(a)){if((a>>i)&1) c++;} return c;} templatevoid pl(T x){cout << x << " ";} templatevoid pr(T x){cout << x << endl;} template inline void pr(T Tar, Ts... ts) { std::cout << Tar << " "; pr(ts...); return; } templatevoid prvec(vector& a){if(a.size()>0){rep(i, (int)a.size()-1){pl(a[i]);} pr(a.back());}else{pr("");}} templatevoid prarr(arr& a){rep(i, (int)a.size()) if(a[i].empty()) pr(""); else prvec(a[i]);} templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b void Fill(A (&array)[N], const T &val){fill( (T*)array, (T*)(array+N), val );} // modint: mod 計算を int を扱うように扱える構造体 template class modint{ public: ll val=0; //コンストラクタ modint(ll x=0){while(x<0)x+=mod;val=x%mod;} //コピーコンストラクタ modint(const modint &r){val=r.val;} //算術演算子 modint operator -(){return modint(-val);} //単項 modint operator +(const modint &r){return modint(*this)+=r;} modint operator -(const modint &r){return modint(*this)-=r;} modint operator *(const modint &r){return modint(*this)*=r;} modint operator /(const modint &r){return modint(*this)/=r;} //代入演算子 modint &operator +=(const modint &r){ val+=r.val; if(val>=mod)val-=mod; return *this; } modint &operator -=(const modint &r){ if(valval==r.val;} bool operator <(const modint& r){return this->valval<=r.val;} bool operator >(const modint& r){return this->val>r.val;} bool operator >=(const modint& r){return this->val>=r.val;} bool operator !=(const modint& r){return this->val!=r.val;} }; using mint = modint; //入出力ストリーム istream &operator >>(istream &is,mint& x){//xにconst付けない ll t;is >> t; x=t; return (is); } ostream &operator <<(ostream &os,const mint& x){ return os< arr modpowmat(arr &a, ll n){ int s = a.size(); arr b(s, vector(s, 0)); rep(i, s) b[i][i] = 1; while(n>0){ if(n&1) { arr c(s, vector(s, 0)); rep(i, s) rep(j, s) rep(k, s) c[i][j] += a[i][k] * b[k][j]; b = c; } arr c(s, vector(s, 0)); rep(i, s) rep(j, s) rep(k, s) c[i][j] += a[i][k] * a[k][j]; a = c; n >>= 1; } return b; } //二項係数の計算 #define MAXR 300000 mint fac[MAXR+1],finv[MAXR+1],inv[MAXR+1]; //テーブルの作成 void COMinit() { fac[0]=fac[1]=1; finv[0]=finv[1]=1; inv[1]=1; FOR(i,2,MAXR){ fac[i]=fac[i-1]*mint(i); inv[i]=-inv[MOD%i]*mint(MOD/i); finv[i]=finv[i-1]*inv[i]; } } //演算部分 mint PER(ll n, ll k){ if(n> s; int n = s.size(); arr dp(n+1, vector(2, 0)); rep(i, n) FOR(j, 1, 10){ int p = s[i] - '0'; if(p > j){ dp[i+1][0] += (dp[i][0] + dp[i][1])*j; dp[i+1][0] += j; }else if(p==j){ dp[i+1][0] += (dp[i][0])*j; if(i>0) dp[i+1][0] += j; if(i>0) dp[i+1][1] = dp[i][1]*j; else dp[i+1][1] = j; }else{ dp[i+1][0] += (dp[i][0])*j; if(i>0) dp[i+1][0] += j; } } // prarr(dp); pr(dp[n][0] + dp[n][1]); return 0;}