#include using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair P; #define fi first #define se second #define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++) #define rep(i,n) repl(i,0,n) #define all(x) (x).begin(),(x).end() #define dbg(x) cout<<#x"="<y?x:y) #define mmin(x,y) (x vec; typedef vector mat; struct Matrix{ int N; mat a; Matrix(int n){ N=n; a=mat(N,vec(N)); for(int i=0;i0;b>>=1,d=d*d)if(b&1)res=d*res; return res; } Matrix operator+(const Matrix& r) const { Matrix s(N); for(int i=0;i=modl)s[i][j]-=modl; } } for(int j=0;j& operator[](int i){ return a[i]; } }; ll fib(ll n){ Matrix a(2); a[0][0]=1; a[0][1]=1; a[1][0]=1; a[1][1]=0; Matrix res=a.pow(n); return res[0][0]; } int main(){ ll n; cin>>n; cout<