#include #include #include #include #include #include #include #include #include #include #define mkp make_pair #define mkt make_tuple #define rep(i,n) for(int i = 0; i < (n); ++i) #define all(v) v.begin(),v.end() using namespace std; typedef long long ll; const ll MOD=1e9+7; template void chmin(T &a,const T &b){if(a>b) a=b;} template void chmax(T &a,const T &b){if(a>N>>K; vector dp(N+1,INF); dp[1]=1; for(int k=0;k ndp=dp; for(int j=0;j<3;j++){ int value=INF; for(int i=j;i<=N;i+=3){ chmin(ndp[i],value); chmin(value,dp[i]); if(value