#include using namespace std; using ll=long long; #define int ll #define FOR(i,a,b) for(int i=int(a);i; using vi=vector; using ld=long double; template ostream& operator<<(ostream& os,const pair& p){ os<<"("< ostream& operator <<(ostream& os,const vector& v){ os<<"["; REP(i,(int)v.size()){ if(i)os<<","; os< void chmax(T& a,U b){ if(a void chmin(T& a,U b){ if(a>b) a=b; } template T Sq(const T& t){ return t*t; } const int inf=LLONG_MAX/3; const int mod=1000000007; struct Mat{ int buf[2][2]; Mat operator*(const Mat& rhs)const{ Mat ret{}; REP(i,2)REP(j,2)REP(k,2) ret.buf[i][j]=(ret.buf[i][j]+buf[i][k]*rhs.buf[k][j])%mod; return ret; } }; void Wafrelka(int n){ if(n==0){ cout<<0<