#include <bits/stdc++.h>
#include "util.h"
#include "modDivide.h"

using namespace std;

//***********************************************************
// HackerRank Prepare > Mathematics > Combinatorics: NcrTable
//***********************************************************

string ltrim(const string &);
string rtrim(const string &);

using TestCasesMap = map<string,tuple<vector<string>,vector<vector<int>>>>;

TestCasesMap testCases = {
    // test   inputs               expected results
    // ----   ------------------   ----------------
    {  "3",   { {"2","4","5"},     { {1,2,1}, {1,4,6,4,1}, {1,5,10,10,5,1}} } },
    {  "1",   { {"229"},           { {1,229,26106,1975354,111607501,22337545,500601680,233453520}} } },
    //{  "1",   { {"22"},           { {1,22,231,1540,7315,26334,74613,170544,319770,497420,646646,705432,646646,497420,319770,170544,74613,26334,7315,1540,231,22,1}} } },

                
};

TestCasesMap::const_iterator testCase = testCases.find("1");

/*
 * Complete the 'solve' function below.
 *
 * The function is expected to return an INTEGER_ARRAY.
 * The function accepts INTEGER n as parameter.
 */

static constexpr long MOD = (long) pow(10, 9);

vector<int> solve(int n) {
    cerr << n << endl;

    auto NCR = [](int n, int r) -> long
    {
        // recursive lambda
        auto NCR_impl = [](int n, int r, auto& NCR_ref) -> long
        {
            if (r == 0) return 1;

            /*
              Extra computation saving for large R,
              using property:
              N choose R = N choose (N-R)
            */
            if (r > n / 2) return NCR_ref(n, n - r, NCR_ref); 

            long res = 1;

            for (int k = 1; k <= r; ++k)
            {
                //res *= n - k + 1;
                res = (res * (n - k + 1)) % MOD;                
                res /= k;
            }

            cerr << res << endl;
            return res;// % MOD;
        };

        return NCR_impl(n, r, NCR_impl);
    };
    
    vector<int> arr;

    for (int r = 0; r <= 11; r++)
        arr.push_back(NCR(n, r));

    return arr;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string t_temp;
    if (outputMode == OutputMode::HackerRank)
        getline(cin, t_temp);
    else
        t_temp = testCase->first;    

    int t = stoi(ltrim(rtrim(t_temp)));

    for (int t_itr = 0; t_itr < t; t_itr++) {
        string n_temp;
        if (outputMode == OutputMode::HackerRank)
            getline(cin, n_temp);
        else
            n_temp = get<0>(testCase->second)[t_itr];

        int n = stoi(ltrim(rtrim(n_temp)));

        vector<int> result = solve(n);

        cerr << "expected: ";
        for (auto& i: get<1>(testCase->second)[t_itr])
            cerr << i << " ";
        cerr << endl;

        cerr << "  actual: ";
        for (size_t i = 0; i < result.size(); i++) {
            cerr << result[i] << " ";
            fout << result[i];

            if (i != result.size() - 1) {
                fout << " ";
            }
        }

        cerr << endl;
        fout << "\n";
    }

    fout.close();

    return 0;
}