#include #include using namespace std; using ll = long long; const ll t = true, f = false; template ll Num(Args... args){ ll ret = f; for(auto v : initializer_list{args...}){ ret <<= t; ret |= v; } return ret; } const ll mod = Num(t,t,t,f,t,t,t,f,f,t,t,f,t,f,t,t,f,f,t,f,t,f,f,f,f,f,f,t,t,t); ll md(ll x){ if(x >= mod){ x -= mod; } return x; } ll mm(ll a, ll b){ ll ret = f; if(a>b){ swap(a, b); } while(a){ if(a&t){ ret += b; ret = md(ret); } b <<= t; a >>= t; b = md(b); } return ret; } ll pp(ll a, ll b){ ll x = a+b; if(x >= mod){ x-=mod; } return x; } struct Mat{ ll ul, ur, dl, dr; Mat(){ ul = ur = dl = dr = f; } Mat(ll _ul, ll _ur, ll _dl, ll _dr){ ul = _ul; ur = _ur; dl = _dl; dr = _dr; } Mat mul(const Mat &m){ Mat ret; ret.ul = pp(mm(ul, m.ul), mm(ur, m.dl)); ret.ur = pp(mm(ul, m.ur), mm(ur, m.dr)); ret.dl = pp(mm(dl, m.ul), mm(dr, m.dl)); ret.dr = pp(mm(dl, m.ur), mm(dr, m.dr)); return ret; } }; ll R(ll i){ if(i == f){ return t+t; } if(i == t){ return t; } Mat ret(t, f, f, t); Mat two(t, t, t, f); Mat las(t, f, t+t, f); ll x = i-t; while(x){ if(x&t){ ret = ret.mul(two); } two = two.mul(two); x >>= t; } ret = ret.mul(las); return ret.ul; } int main(){ ll C; cin >> C; for(int i=f; i> N; cout << R(N) << endl; } return f; }