int vis[N+],prim[N+];

 int cnt;

 void Eular()

 {

     vis[]=vis[]=;

     for(int i=;i<N;i++)

         if(!vis[i])

         {

             prim[cnt++]=i;

             for(ll j=(ll)i*i;j<N;j+=i) vis[j]=;

         }

 }

 ll ans,re;

 void e_gcd(ll a,ll b)

 {

     if(b==)

     {

         ans=,re=;

         return;

     }

     e_gcd(b,a%b);

     ll temp=ans;

     ans=re; ///***

     re=temp-a/b*re;

 }

 int vis[N];

 bool spfa_bfs()

 {

     ans[s]=v;

     vis[s]=;

     queue<int> qu;

     qu.push(s);

     while(!qu.empty())

     {

         int node=qu.front();

         qu.pop();

         vis[node]=;

         for(int i=;i<=n;i++)

         {

             if(ans[i]<(ans[node]-ma2[node][i])*ma1[node][i])

             {

                 ans[i]=(ans[node]-ma2[node][i])*ma1[node][i];

                 if(ans[s]>v) return true;

                 if(!vis[i]) qu.push(i),vis[i]=;

             }

         }

     }

     return false;

 }

 int ma[N][N];

 int n,m;

 inline int lowbit(int x){return x&-x;}

 void updata(int x,int y)

 {

     for(int i=x;i<=n;i+=lowbit(i))

         for(int j=y;j<=m;j+=lowbit(j)) ma[i][j]++;

 }

 int query(int x,int y)

 {

     int res=;

     for(int i=x;i>;i-=lowbit(i))

         for(int j=y;j>;j-=lowbit(j)) res+=ma[i][j];

     return res;

 }

 int n;

 struct p{

     double matris[][];

 }Rl,tep,res,wat,ans;

 void init()

 {

     memset(Rl.matris,,sizeof(Rl.matris));

     memset(res.matris,,sizeof(res.matris));

     memset(tep.matris,,sizeof(tep.matris));

     memset(wat.matris,,sizeof(wat.matris));

     for(int i=;i<=n;i++) tep.matris[i][i]=;

 }

 p Matris(p a,p b)

 {

     p tem;

     memset(tem.matris,,sizeof(tem.matris));

     for(int i=;i<=n;i++)

         for(int j=;j<=n;j++)

             for(int k=;k<=n;k++)

                 tem.matris[i][j]+=a.matris[i][k]*b.matris[k][j];

     return tem;

 }

 p quick_mi(ll n)

 {

     p m=Rl,b=tep;

     while(n)

     {

         if(n&) b=Matris(b,m);

         m=Matris(m,m);

         n/=;

     }

     return b;

 }