#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair P; ll MOD; ll solve(string s){ int n=s.size(); if(n==1) return s[0]-'0'; ll dp[2][100010]={}; dp[0][0]=1, dp[1][0]=s[0]-'0'-1; for(int i=1; is[n-1-i]) break; else if(s[i]>s; MOD=1e9; cout<