#include #define ALL(v) std::begin(v),std::end(v) using lint=long long; using lubl=long double; lint mod=1'000'000'007; struct mint{ lint value; mint()=default; mint(lint x):value(x){} }; std::ostream&operator<<(std::ostream&os,mint x){return os<>n; std::vector>dp(n+1,std::vector(4)); for(lint i=1;i<=std::min(3ll,n);i++)dp.at(i).at(i)=1; for(lint i=1;i