#include 
#include 
#include 
using namespace std;
typedef long long ll;
typedef vector> matrix;
typedef vector> d_matrix;
const int maxn = 1e5 + 10;
const int INF = 2e9;
const ll MOD = 998244353;
void print(matrix A) {
    int n = (int) A.size(), m = (int) A[0].size();
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cout << A[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}
void print(d_matrix A) {
    int n = (int) A.size(), m = (int) A[0].size();
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cout << A[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}
matrix multiply_by_k(matrix A, int k) {
    matrix res = A;
    int n = (int) A.size(), m = (int) A[0].size();
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            res[i][j] *= k;
        }
    }
    return res;
}
matrix add_two_matrices(matrix A, matrix B) {
    int n_a = (int) A.size(), m_a = (int) A[0].size();
    int n_b = (int) B.size(), m_b = (int) B[0].size();
    
    if(n_a == n_b and m_a == m_b) {
        matrix res = A;
        for(int i = 0; i < n_a; i++) {
            for(int j = 0; j < m_a; j++) {
                res[i][j] = A[i][j] + B[i][j];
            }
        }
        return res;
    }
    cout << "Dimenziite na matricite treba da se isti za da mozhe da gi sobereme istite" << endl;
    return {{0}};
}
matrix subtract_two_matrices(matrix A, matrix B) {
    int n_a = (int) A.size(), m_a = (int) A[0].size();
    int n_b = (int) B.size(), m_b = (int) B[0].size();
    
    if(n_a != n_b or m_a != m_b) {
        cout << "Dimenziite na matricite treba da se isti za da mozhe da gi sobereme istite" << endl;
        return {{0}};
    }
    matrix res = A;
    for(int i = 0; i < n_a; i++) {
        for(int j = 0; j < m_a; j++) {
            res[i][j] = A[i][j] - B[i][j];
        }
    }
    return res;
}
matrix multiply_two_matrices(matrix A, matrix B) {
    int n_a = (int) A.size(), m_a = (int) A[0].size();
    int n_b = (int) B.size(), m_b = (int) B[0].size();
    
    if(m_a != n_b) {
        cout << "Matricite ne mozhat da se mnozhat" << endl;
        return {{0}};
    }
    matrix res(n_a, vector(m_b, 0));
    for(int i = 0; i < n_a; i++) {
        for(int j = 0; j < m_b; j++) {
            int c = 0;
            for(int k = 0; k < n_a; k++) {
                c += (A[i][k] * B[k][j]) % MOD;
                c %= MOD;
            }
            res[i][j] = c % MOD;
        }
    }
    
    return res;
}
int determinant_of_matrix(matrix A) {
    int sz = (int) A.size();
    if(sz == 2) {
        return (A[0][0] * A[1][1]) - (A[0][1] * A[1][0]);
    }
    int determinant = 0;
    int sign = 1;
    for(int i = 0; i < sz; i++) {
        int n = 0, m = 0;
        
        matrix tmp(sz - 1, vector(sz - 1, 0));
        for(int j = 0; j < sz; j++) {
            for(int k = 0; k < sz; k++) {
                if(j != 0 and k != i) {
                    tmp[n][m] = A[j][k];
                    if(m < sz - 2) {
                        m++;
                    }
                    else {
                        m = 0;
                        n++;
                    }
                }
            }
            
        }
        determinant = determinant + sign*(A[0][i]) * determinant_of_matrix(tmp);
        sign *= -1;
    }
    return determinant;
}
matrix transpose_matrix(matrix A) {
    int n = (int) A.size();
    int m = (int) A[0].size();
    matrix res(m, vector(n));
    
    for(int j = 0; j < m; j++) {
        for(int i = 0; i < n; i++) {
            res[j][i] = A[i][j];
        }
    }
    
    return res;
}
d_matrix inverse_of_matrix(matrix A) {
    int n = (int) A.size();
    int m = (int) A[0].size();
    d_matrix res(n, vector(m));
    
    matrix adj_matrix(n, vector(m));
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            matrix minor(n - 1, vector(m - 1));
            int r = 0, c = 0;
            for(int a = 0; a < n; a++) {
                if(a == i) continue;
                for(int b = 0; b < m; b++) {
                    if(a == i or b == j) continue;
                    minor[r][c] = A[a][b];
                    c++;
                }
                c = 0;
                
                r++;
            }
            adj_matrix[i][j] = determinant_of_matrix(minor);
            if((i + j) % 2 == 1) {
                adj_matrix[i][j] *= -1;
            }
        }
    }
    adj_matrix = transpose_matrix(adj_matrix);
    double det = determinant_of_matrix(A);
    cout << det << endl;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            res[i][j] = (1.0 / det) * adj_matrix[i][j];
        }
    }
    
    return res;
}


ll power(ll a, ll b) {
    ll res = 1;
    while(b) {
        if(b % 2 == 1) {
            res *= a;
        }
        a *= a;
        b /= 2;
    }
    return res;
}
ll nth_fibbonaci_number(ll x) {
    matrix A = {
        {1, 1},
        {1, 0}
    };
    matrix B = A;
//    for(int i = 0; i < x; i++) {
//        A = multiply_two_matrices(A, B);
//    }
    matrix res = {
        {1, 0},
        {0, 1}
    };
    while(x) {
        if(x % 2 == 1) {
            res = multiply_two_matrices(res, A);
        }
        A = multiply_two_matrices(A, A);
        x /= 2;
    }
    
    return res[0][0];
}

int main() {
//    nth_fibbonaci_number(8);
//    return 0;
    for(int i = 1; i <= 10; i++) {
        cout << nth_fibbonaci_number(i) << " ";
    }
    return 0;
}