#include using namespace std; #define ALL(x) x.begin(),x.end() #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<bool chmax(T &a,const T &b){if(abool chmin(T &a,const T &b){if(bn-r) r=n-r; if(r==0) return 1; ll a=1; //a=n!/(n-r)!=n~n-r+1までの総積->O(r) for(ll i=0;i>n; ll m=n-4; m%=mod; ll ans=((m+3)/3)%mod; ll k=ans; if(m%3==1){ ans+=f(0,(k+1)/2);ans%=mod; ans+=f(2,k/2);ans%=mod; } else if(m%3==0){ ans+=f(0,(k+1)/2);ans%=mod; ans+=f(1,k/2);ans%=mod; } else{ ans+=f(1,(k+1)/2);ans%=mod; ans+=f(2,k/2);ans%=mod; } cout<