/*
    simple recursion dp
    dp[i] => number of ways to make the target sum i
*/



#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7; 
ll f(ll target, vector<ll>&dp){
    if(target==0) return 1;
    if(dp[target]!=-1) return dp[target];
    ll ans = 0;
    for(int i=1; i<=6; i++){
        if(target-i >=0)
        ans = ((ans%mod)+(f(target-i,dp)%mod))%mod;
    }
    return dp[target] = ans;
}
int main(){
    ll target;
    cin >> target;
    vector<ll>dp(target+1,-1); 
    cout << f(target,dp);
}

/*
    simple recursion dp
    dp[i] => number of ways to make the target sum i
*/



#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7; 
ll f(vector<ll>&nums, ll target, vector<ll>&dp){
    if(target==0) return 0;
    if(dp[target]!=-1) return dp[target];
    ll ans = INT_MAX;
    for(ll i=0; i<nums.size(); i++){
        if(target-nums[i] >= 0)
        ans = min(ans,f(nums,target-nums[i],dp)+1);
    }
    return dp[target] = ans;
}
int main(){
    ll n,target;
    cin >> n >> target;
    vector<ll>nums(n);
    for(int i=0; i<n; i++){
        cin >> nums[i];
    }
    sort(nums.begin(),nums.end());
    vector<ll>dp(target+1,-1); 
    ll ans = f(nums,target,dp);
    if(ans == INT_MAX) cout << -1;
    else cout << ans;
}

/*
    simple recursion dp
    dp[i] => number of ways to make the target sum i
*/



#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7; 
ll f(vector<ll>&nums, ll target, vector<ll>&dp){
    if(target==0) return 1;
    if(dp[target]!=-1) return dp[target];
    ll ans = 0;
    for(ll i=0; i<nums.size(); i++){
        if(target-nums[i] >= 0)
        ans = ((ans%mod)+(f(nums,target-nums[i],dp))%mod)%mod;
    }
    return dp[target] = ans;
}
int main(){
    ll n,target;
    cin >> n >> target;
    vector<ll>nums(n);
    for(int i=0; i<n; i++){
        cin >> nums[i];
    }
    sort(nums.begin(),nums.end());
    vector<ll>dp(target+1,-1); 
    ll ans = f(nums,target,dp);
    cout << ans;
}

/*
    The key difference between this problem and Coin Combinations I is that we're now trying to find the number of ordered ways to add the coins to x

    iterate through the given array and find the number of ways to create sum = x by the array indexed b/w 0 and i

    Keep updating the dp
*/



#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7; 

int main(){
    ll n,target;
    cin >> n >> target;
    vector<ll>nums(n);
    for(int i=0; i<n; i++){
        cin >> nums[i];
    }
    sort(nums.begin(),nums.end());
    vector<ll>dp(target+1,0); 
    for(ll i=0; i<n; i++){
        for(ll j = 0; j<=target;j++){
            if(j==0) dp[j]=1;
            else{
                if(j-nums[i]>=0){
                    dp[j] += dp[j-nums[i]];
                    dp[j] %=mod;
                }
            }
        }
    }
    cout << dp[target];
}

/*
    dp[i] => number of moves to make i, 0
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll kth_digit(ll n, ll k){
    k--;
    while(k--){
        n /= 10;
    }
    return n%10;
}
ll f(ll n, vector<ll>&dp){
    if(n==0) return 0;
    if(dp[n]!=-1) return dp[n];
    ll max_digit = 0;
    for(ll i = 7; i>=1; i--){
        max_digit = max(max_digit,kth_digit(n,i));
    }
    ll ans = f(n-max_digit, dp)+1; // be GREEDY :)
    return dp[n] = ans;
}

int main(){
    ll n;
    cin >> n;
    vector<ll>dp(n+1,-1);
    cout << f(n,dp);
}

/*
    dp[i][j] => number of paths till possition i,j;

*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
ll f(ll n, vector<vector<char>>&mat, ll i, ll j, vector<vector<ll>>&dp){
    if(i<0 || i>=n || j<0 || j>=n){
        return 0;
    }
    if(mat[i][j]=='*') return 0;
    if(dp[i][j]!=-1) return dp[i][j];
    ll op1 = f(n, mat,i-1,j,dp);
    ll op2 = f(n, mat,i,j-1,dp);
    dp[i][j] = (op1 + op2)%mod;
    return dp[i][j];
}

int main(){
    ll n;
    cin >> n;
    vector<vector<char>>mat(n,vector<char>(n));
    for(ll i=0; i<n; i++){
        for(ll j=0; j<n; j++){
            cin >> mat[i][j];
        }
    }
    vector<vector<ll>>dp(n,vector<ll>(n,-1));
    dp[0][0] = 1; // you are already on 0,0 so there is one way to be on 0,0.
    cout << f(n,mat,n-1,n-1,dp);
}

/*
    dp[i][j] => 1 based indexed.
    dp[i][j] => max No. of pages till ind i using target money of j
    Recurrsive dp may give MLE in this question so convert it to iterative approach/Bottom-Up.

    This problem has a very strict time and memory limit so do not use array, long long and the recurrsive solution.
*/

#include <bits/stdc++.h>
using namespace std;


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, target;
    cin >> n >> target;
    vector<int>cost(n);
    vector<int>pages(n);
    for(int i=0; i<n; i++){
        cin >> cost[i];
    }
    for(int i=0; i<n; i++){
        cin >> pages[i];
    }
    vector<vector<int>>dp(n+1,vector<int>(target+1,0));
    for(int i = 1; i<=n; i++){
        for(int j = 0; j<=target; j++){
            dp[i][j] = dp[i-1][j];
            if(j-cost[i-1]>=0)
            dp[i][j] = max(dp[i][j],dp[i-1][j-cost[i-1]]+pages[i-1]);
        }
    }
    cout << dp[n][target];
}

/*
    dp[i][prev] => number of ways to satisfy the condition till ind i of array when array[i-1] == prev; 
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
ll mod = 1000000007;

vector<ll>v;
ll n,m;
ll dp[100001][101];
ll solve(ll i, ll prev){
    if(i==n) return 1;
    ll ans =0;
    if(dp[i][prev]!=-1) return dp[i][prev];
    if(v[i]==0){
        if(prev==0){
            for(ll k=1;k<=m; k++){
                ans=(ans +  solve(i+1,k))%mod;
            }
        }else{
            for(ll k=max(ll(1),prev-1); k<=min(prev+1,m); k++){
                ans =(ans +  solve(i+1,k))%mod;
            }
        }
    }else{
        if(prev==0 || abs(prev-v[i])<=1){
            ans=(ans + solve(i+1,v[i]))%mod;
        }else{
            ans = 0;
        }
    }
    return dp[i][prev] = ans;
 
}
int main()
{
    fastio;
    ll t=1;
    // cin>>t;
    while(t--)
    {
        memset(dp,-1,sizeof(dp));
        
        cin >>n>>m;
        
        for(int i=0; i<n; i++){
            ll x;
            cin >> x;
            v.push_back(x);
        }
        ll ans = solve(0,0);
        cout << ans ;
    }
}

/*
    I have divided the filling in two types -
        1. [ ][ ]   (represented by ind 0)
        2. [    ]   (represented by ind 1)
    dp[i][t] => number of ways to fill till i such that i is of type t+1;
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

ll mod = 1000000007;

const ll N = 1e6+1;
vector<vector<ll>>dp(N,vector<ll>(2,-1));
ll solve(ll i, ll j){
    if(i==1) return dp[i][j]=1;
    if(dp[i][j]!=-1) return dp[i][j];
    ll ans0, ans1 ;
    ans0 = ((4*solve(i-1,0)%mod)+(solve(i-1,1)%mod))%mod;
    ans1 = ((2*solve(i-1,1))%mod+(solve(i-1,0)%mod))%mod;
    dp[i][0] = ans0;
    dp[i][1] = ans1;
    return dp[i][j];
}
 
 
int main()
{
    fastio;
    ll t=1;
    cin>>t;
    while(t--)
    {
        ll k;
        cin >> k;
        ll ans = (solve(k,0)%mod+solve(k,1)%mod)%mod;
        cout << ans << endl;
    }
 
}

/*
    dp[i][j] => min num of opreartions to match i indexes of word1 to j indexes of word2. 
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int f(string &s1, string &s2, ll i, ll j, vector<vector<ll>>&dp){
    if(i<0) return j+1;
        if(j<0) return i+1;
        if(dp[i][j]!=-1) return dp[i][j];
        if(s1[i]==s2[j]) return dp[i][j]=f(s1,s2,i-1,j-1,dp);
        int del = 1+f(s1,s2,i-1,j,dp);
        int rep = 1+f(s1,s2,i-1,j-1,dp);
        int ins = 1+f(s1,s2,i,j-1,dp);
        int m = min(del,rep);
        m = min(m,ins);
        return dp[i][j]=m;
}

int main(){
    string word1,word2;
    cin >> word1 >> word2;
    vector<vector<ll>>dp(5001,vector<ll>(5001,-1));
    ll ans = f(word1,word2,word1.length(),word2.length(),dp);
    cout << ans;
}

/*
    dp[i][j] => ans for ixj rectagle
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll f(ll a, ll b, vector<vector<ll>>&dp){
    if(a==b) return 0;
    if(dp[a][b]!=-1)return dp[a][b];
    ll ans  = INT_MAX;
    for(ll i=1; i<b; i++){
        ans = min(ans,f(a,i,dp)+f(a,b-i,dp)+1);
    }
    for(ll i=1; i<a; i++){
        ans = min(ans,f(i,b,dp)+f(a-i,b,dp)+1);
    }
    dp[b][a] = ans;
    return dp[a][b] = ans;
}
int main(){
    ll a, b;
    cin >> a >> b;
    ll k = max(a,b);
    vector<vector<ll>>dp(k+1,vector<ll>(k+1,-1));
    cout << f(a,b,dp);
}

/*
    hehe :) solved it using sets but if you have a dp solution do it otherwise this works just fine and it reminds you to keep using the data structures.....

*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
        ll n;
        cin >> n;
        vector<ll>v(n);
        for(auto &i : v)cin >> i;
        set<ll>s;
        for(auto &i:v){
            set<ll>a;
            for(auto &as: s){
                a.insert(as+i);
            }
            for(auto &ss: a){
                s.insert(ss);
            }
            s.insert(i);
        }
        cout << s.size() << endl;
        for(auto ss: s){
            cout << ss << " ";
        }
}

/*
    dp[i][j] => max possible score when arr is concidered from index i to j

    Basically just concider that both play optimally so the opponent always tries to minimize the score while the player tries to maximise it;
*/


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<ll>v;
ll n;
vector<vector<ll>>dp(5001,vector<ll>(5001,-1));

ll solve(ll i, ll j){
    if(j-i==1){
        if((n-(j-i+1))&1){
            return dp[i][j]=min(v[i],v[j]);
        }
        else{
            return dp[i][j]=max(v[i],v[j]);
        }
    }
    if(dp[i][j]!=-1) return dp[i][j];
    ll ans;
    if((n-(j-i+1))&1){
        ans = min(solve(i+1,j),solve(i,j-1));
 
    }else{
        ans = max(solve(i+1,j)+v[i],solve(i,j-1)+v[j]);
    }
    return dp[i][j]=ans;
}
 
 
int main()
{
    cin >> n;
    for(ll i=0; i<n; i++){
        ll x;
        cin >> x;
        v.push_back(x);
    }
    ll ans = solve(0,n-1);
    cout << ans;
 
}

/*
    dp[i][j] => number of ways till index i-1, to make sum of j
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod = 1000000007;

int main(){
    ll n;
    cin >> n;
    ll sum = (n*(n+1))/2;
    if(sum&1){              // if sum is odd n possible solution
        cout << 0 ;
        return 0;
    }
    
    sum = sum/2;
    ll k=(n*(n+1))/4+1;     // max value of sum/2
    vector<vector<ll>>dp(n+1,vector<ll>(k));
    
    dp[0][0]=1;
    for(ll i=1; i<k;i++)dp[0][i]=0;     // base case
    
    for(ll i=1; i<n+1; i++){
        for(ll j=0; j<k; j++){
            if(j<i) dp[i][j] = dp[i-1][j]%mod;
            else dp[i][j] = (dp[i-1][j-i]+dp[i-1][j])%mod;
        }
    } 
    cout << (dp[n][sum]*500000004)%mod; // 500000004 => inverse modulus of 2;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    ll n;
    cin >> n;
    vector<ll>v(n);
    for(ll i=0; i<n; i++){
        cin >>v[i];
    }
    vector<ll>tem;
    ll ans = 0;
    for(ll i=0;i<n;i++){
        if((tem.size()==0) || (tem[tem.size()-1]<v[i])){
            tem.push_back(v[i]);
        }
        else{
            auto lb = lower_bound(tem.begin(),tem.end(),v[i]);
            tem[lb - tem.begin()] = v[i];
        }
    }
    cout << tem.size();
}

/*
    Code is self Explainatory yet have doubts do comment and ask
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll N = 2e5+2;
ll dp[N];
ll f(vector<pair<ll,pair<ll,ll>>>&v, ll i){
    if(dp[i]!=-1)return dp[i];
    ll st = v[i].second.first;
    ll ans = v[i].second.second;
    pair<ll,pair<ll,ll>>temp = {st,{0,0}};
    auto lb = lower_bound(v.begin(),v.end(),temp);
    if(lb-v.begin()!=0){
        ans += f(v,lb-v.begin()-1);
    }
    if(i!=0)
    ans = max(ans,f(v,i-1));
    return dp[i] = ans;
}
int main(){
    ll n;
    cin >> n;
    memset(dp,-1,sizeof(dp));
    vector<pair<ll,pair<ll,ll>>>v;
    for(ll i=0; i<n; i++){
        ll a,b,m;
        cin >> a >> b >> m;
        v.push_back({b,{a,m}});
    }
    sort(v.begin(),v.end());
    cout << f(v,n-1);
}

/*
    if mask = 0 1 0  ->  1st indexed person reached the top ;
    dp[mask][0] = in the state of 'mask' min no of trips
    dp[mask][1] = in the state of 'mask' min weight of the last trip
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    ll n, x;
    cin >> n >> x;
    vector<ll>weight(n);
    for(int i=0; i<n;i++){
        cin >> weight[i];
    }
    vector<vector<ll>>dp(1<<n+1,vector<ll>(2,0));
    for(ll mask=1; mask<(1<<n); mask++){
        dp[mask] = {INT_MAX, INT_MAX};
        for(ll j = 0 ; j < n; j++){
            if(mask & (1<<j)){
                ll n_mask = mask^(1<<j);
                auto temp = dp[n_mask];
                if(temp[1] + weight[j] <= x){
                    temp[1] = temp[1] + weight[j];
                }
                else{
                    temp[0]++;
                    temp[1] = weight[j];
                }
                dp[mask] = min(dp[mask],temp);
            }
        }
    }
    if(dp[(1<<n)-1][1]==0){
        cout << dp[(1<<n)-1][0];
    }else{
        cout << dp[(1<<n)-1][0]+1;
    }
}

/*
    dp with bitmasking
    dp[ind][mask] => filling col == ind while the mask of col is 'mask' 
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
void gm (ll curr, ll nxt, vector<ll>&new_masks, ll n, ll ind){
    if(ind==n) {
        new_masks.push_back(nxt);
        return;
    }
    if(ind>n) return;
    if((curr & (1<<ind))!=0){
        gm(curr,nxt,new_masks,n,ind+1);
    }
    if(ind!=n-1){
        if(((curr & (1<<ind))==0) && ((curr & (1<<(ind+1)))==0)){
            gm(curr,nxt,new_masks,n,ind+2);
        }
    }
    
    if((curr & (1<<ind))==0){
        gm(curr,nxt+(1<<ind),new_masks,n,ind+1);
    }
}
int f(ll n, ll m, vector<vector<ll>>&dp, ll ind, ll mask){
    if(ind == m){
        if(mask==0) return 1;
        return 0;
    }
    if(dp[ind][mask]!=-1)return dp[ind][mask];
    ll ans = 0;
    vector<ll>new_masks;
    gm(mask,0,new_masks,n,0);
    for(auto n_mask: new_masks){
        ans = ((ans%mod)+f(n,m,dp,ind+1,n_mask))%mod;
    }
    return dp[ind][mask] = ans%mod;

}
int main(){
    ll n,m;
    cin >> n >> m;
    vector<vector<ll>>dp(m+1, vector<ll>((1<<n)+1,-1));
    cout << f(n,m,dp,0,0);
}

/*
    dp(N,x,leading_z,tight)
    standard problem of Digit_DP
*/


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll dp[20][10][2][2];
ll f(string &b, ll n, ll x, bool leading_z, bool tight){
    if(n==0) return 1;
    if(x!=-1 && dp[n][x][leading_z][tight]!=-1) return dp[n][x][leading_z][tight];
    ll lb = 0;
    ll ub = tight ? (b[b.length()-n]-'0'): 9;
    ll ans = 0;
    for(ll i= lb; i<=ub; i++){
        if(i == x && !leading_z)continue;
        ans += f(b,n-1,i,(leading_z & i==0), (tight & i==ub));
    }
    return dp[n][x][leading_z][tight] = ans;
}

int main(){
    memset(dp,-1,sizeof(dp));
    ll A,B;
    cin >> A >> B;
    string a = to_string(A-1);
    string b = to_string(B);
    ll ans_b = f(b,b.length(),-1,1,1);
    memset(dp,-1,sizeof(dp));
    ll ans_a = f(a,a.length(),-1,1,1);
    cout << ans_b-ans_a;
}