#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10 , mod = 1e9 ; 

int w[22] ; 
// f[i][j] 前i个体积恰好为j的方案数。
int n ; 
int f[N] ; 

int main()
{
    w[1] = 1 ; 
    for(int i = 2 ;  i < 22 ; i ++ ) w[i] = w[i - 1] * 2 ; 
    cin >> n ; 
    // 这是一个完全背包问题
    f[0] = 1 ; 
    for(int i = 1 ; i < 22 ; i ++ ) {
        for(int j = 0 ; j <= n ; j ++ ) {
            if(j >= w[i] )f[j] = ( f[j - w[i]] + f[j] ) % mod ; 
        }
    }
    //cout << "hello" << endl ;
    cout << f[n] << endl ; 
    return 0 ; 
}

#include <iostream>
#include <cstring> 
using namespace std;
const int N = 1010 , M = 2e4 + 10 ; 
int n , m ; 
int v[N] , w[N] , s[N] ; 
int q[M] ; 
int f[2][M] ; // 滚动数组的写法。
int main()
{
    cin >> n >> m ; 
    for(int i = 1; i <= n ; i ++ ) cin >> v[i] >> w[i] >> s[i] ; 

    for(int i = 1 ; i <= n ; i ++ ) // 当前的物品的序号。
    {
        for(int r = 0 ; r < v[i] ; r ++ ) //枚举当前体积的所有的余数，也就是能更新这个状态的所有的前面的状态 
        {
            int hh = 0 , tt = -1 ; // 进行一个单调队列的操作。
            for(int j = r ; j <= m   ; j += v[i] ) 
            {

                if(hh <= tt && j - q[hh]> v[i] * s[i]) hh ++ ; 
                while(hh <= tt && (f[(i - 1) & 1 ][q[tt]] + (j - q[tt]) / v[i] * w[i] )<= f[(i - 1) & 1 ][j] ) tt -- ; 
                q[++tt] = j ;
                f[i & 1 ][j] = f[ (i - 1) & 1 ][q[hh]] + (j - q[hh]) / v[i] * w[i] ; 
            }
        }
    }
    cout << f[n & 1][m] ; 

    return 0 ; 
}

#include <iostream>
#include <vector>
#define x first
#define y second 
using namespace std;
typedef pair<int,int> PII ; 
const int N = 110 ; 

int n , m ; 

int f[N] ; 

vector<PII> s[N] ; 
int main()
{
    cin >> n >> m ; // 组数和容量。

    for(int i = 1 ; i <= n ; i ++ )
    {
        int cnt ; 
        cin >> cnt ; 
        for(int j = 0 ; j < cnt ; j ++ )
        {
            int v , w ; 
            cin >> v >> w ; 
            s[i].push_back({ v , w }) ; 
        }
    }

    for(int i = 1 ; i <= n ; i ++)  // 遍历这个数组。
    {
        for(int j = m ; j >= 1  ; j -- )
        {

            for(int k = 0 ; k < s[i].size() ; k ++ )
            {
                if(j >= s[i][k].x ) f[j] = max(f[j] , f[j - s[i][k].x] + s[i][k].y ) ; 
            }
        }
    }
    cout << f[m] ; 
    return 0 ;     
}

#include <iostream>
using namespace std;
const int N = 1010;
int v[N] , w[N] ; 

int n , m ;

int f[N] ; // f[i][j] 前i件物品体积不超过j的情况下 能够得到的最大的价值。

int main()
{
    cin >> n >> m ; 
    for(int i = 1; i <= n ; i ++ )
    {
        cin >> v[i] >> w[i] ;
    }

    for(int i = 1 ; i <= n ; i ++ )
    {
        for(int j = 0 ; j <= m ; j ++ ) // 体积可以从0开始循环。
        {
            if(j >= v[i] )f[j] = max(f[j] , f[j - v[i]] + w[i] ) ; 
        }
    }
    cout << f[m] << endl ; 

    return 0 ; 
}

#include <iostream>
#define ios ios::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0)
using namespace std;
const int N = 1010 ; 

int v[N] , w[N] ; 

int n , m ; 

int f[N][N] ; // f[i][j] 表示前i件物品在总体积不超过j的情况下的最大的价值。


int main()
{
    ios; 
    cin >> n >> m ; 
    for(int i = 1 ; i <= n ; i ++ )
    {
        int a , b ;
        cin >> a >> b ; 
        v[i] = a , w[i] = b ; 
    }
    for(int i = 1 ; i <= n ; i ++ )
    {
        for(int j = 1 ; j <= m ; j ++ )
        {
            f[i][j] = f[i - 1][j] ; 
            if(j >= v[i] ) f[i][j] = max(f[i][j] , f[i - 1][j - v[i]] + w[i] ) ;  
        }
    }
    cout << f[n][m] << endl ; 
    return 0 ; 
}

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int T ;
    cin >> T;
    while(T -- ) 
    {
        int n;
        cin >> n ; 
        int minv = 2e9  ; 
        vector<int> a(n) ;
        for(int i = 0 ; i < n ; i ++ ) 
        {
            cin >> a[i] ;
            minv = min(a[i] , minv ) ;    
        } 
        if(minv == a[0] ) puts("Bob") ;
        else puts("Alice") ; 
    }
    return 0 ; 
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10 ; 
using LL = long long ; 
int n ; 
int prime[N] , cnt ;  
bool st[N] ; 
unordered_map<LL , int>  mp ; 
void get_prime() 
{
    for(int i = 2 ; i <= 1e6 ; i ++ )
    {
        if(!st[i]) prime[cnt++] = i ; 
        for(int j = 0 ; prime[j] <= 1e6 / i ; j ++ ) 
        {
            st[prime[j] * i ] = true ; 
            if(i % prime[j] == 0 ) break ;
        }   
    } 
}


int main()
{
    int n ; 
    cin >> n ; 
    get_prime() ; 
    for(int i = 0 ; i < cnt ; i ++ ) mp[(LL)prime[i] * prime[i]] ++ ; 
    for(int i = 0 ; i < n ; i ++ ) {
        LL a ;
        cin >> a ;
        if(mp[a] ) puts("YES") ;
        else puts("NO") ; 
    }
    return 0 ; 
}

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a , b , c , d ;
    cin >> a >> c >> b >> d ;
    cout << max(abs(a - b ) , abs(c - d ) ) ; 
    return 0 ; 
}

#include <bits/stdc++.h>
using namespace std ; 
const int N = 2010 , M = 6010 ; 
int h[N] , ne[M] , e[M] , idx; 
int n , m , k ; 
int f[N] ; // 记录当前节点是必胜态还是必败态。
void add(int a , int b ) 
{
    e[idx] = b ,  ne[idx] = h[a] , h[a] = idx ++ ; 
}

int SG(int x ) 
{
    if(f[x] != -1 ) return f[x] ; 
    unordered_set<int> S ; 
    for(int i = h[x] ; ~i ; i = ne[i] ) 
    {
        int j = e[i] ; 
        S.insert(SG(j)) ; 
    }
    for(int i = 0 ; ; i ++ ) 
    {
        if(!S.count(i))
        {
            f[x] = i ; 
            return i ; 
        }
    }
}

int main()
{
    cin >> n >> m >> k ;
    memset(h , -1 , sizeof h ) ;
    for(int i = 0 ; i < m ; i ++ ) 
    {
        int a , b ;
        cin >> a >> b ; 
        add(a , b ) ; 
    }
    memset(f , -1 , sizeof f ) ; 

    int res = 0 ; 
    for(int i = 0 ; i < k ; i ++ ) 
    {
        int id ;
        cin >> id;
        res ^= SG(id) ; 
    }
    if( res ) puts("win") ; 
    else puts("lose") ; 
    return 0 ; 
}

#include <bits/stdc++.h>
using namespace std;
const int N = 100 ; 
int f[N] ; 
int n , k ; 
int main()
{
    int T ; 
    cin >> T ;
    while(T -- )
    {
        cin >> n >> k ;
        if(k % 3 == 0 ) 
        {
            int r = n % (k + 1) ; 
            if((r % 3 == 0 ) && r != k ) puts("Bob");
            else puts("Alice") ; 
        }
        else {
            int r = n % 3 ; 
            if(r == 0 ) puts("Bob");
            else puts("Alice") ; 
        }
    }
    return 0 ; 
}