#include using namespace std; typedef long long LL; #define CIN_ONLY if(1) struct cww{cww(){ CIN_ONLY{ ios::sync_with_stdio(false);cin.tie(0); } }}star; #define fin "\n" #define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() #define fi first #define se second #define pb push_back #define DEBUG if(0) #define REC(ret, ...) std::function template inline void chmin(T &l,T r){l=min(l,r);} template inline void chmax(T &l,T r){l=max(l,r);} template istream& operator>>(istream &is,vector &v){ for(auto &it:v)is>>it; return is; } typedef long long LL; typedef LL D; #define S 3 int sz=S; struct M{ D v[S][S]; }mat[64]; const LL mod=1e9+7; void mat_mul(M &a,M& b,M &c){ for(int i=0;i>N; mat[0].v[0][0]=100; mat[0].v[0][1]=0; mat[0].v[0][2]=1; mat[0].v[1][0]=1; mat[0].v[1][1]=0; mat[0].v[1][2]=0; mat[0].v[2][0]=0; mat[0].v[2][1]=0; mat[0].v[2][2]=1; REP(i,63)mat_mul(mat[i],mat[i],mat[i+1]); vector res{1,0,1}; LL M=N-1; for(int b=0;M;M>>=1,b++){ if(M&1){ vector nxt(3,0); REP(i,3)REP(j,3)(nxt[i]+=res[j]*mat[b].v[i][j])%=mod; swap(res,nxt); } } cout<