zoj3256

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<algorithm>
  5 
  6 using namespace std;
  7 typedef long long ll;
  8 const int mo=7777777;
  9 const int has=419;
 10 int b[15],v[15],n,m,t;
 11 struct node
 12 {
 13     int len,st[1010],p[has],nex[1010];
 14     void clr()
 15     {
 16         len=0;
 17         memset(p,255,sizeof(p));
 18     }
 19     int push(int nw)
 20     {
 21         int x=nw%has;
 22         for (int i=p[x]; i>-1; i=nex[i])
 23             if (st[i]==nw) return i;
 24         st[++len]=nw;
 25         nex[len]=p[x]; p[x]=len;
 26         return len;
 27     }
 28 } f;
 29 
 30 struct mat{
 31     int a[150][150];
 32     friend mat operator *(mat a,mat b)
 33     {
 34         mat c;
 35         for (int i=1; i<=t; i++)
 36             for (int j=1; j<=t; j++)
 37             {
 38                 ll s=0;
 39                 for (int k=1; k<=t; k++) s+=(ll)a.a[i][k]*b.a[k][j];
 40                 c.a[i][j]=s%mo;
 41             }
 42         return c;
 43     }
 44 } ans,c;
 45 
 46 void get(int st)
 47 {
 48     for (int i=n-1; i>=0; i--)
 49     {
 50         b[i]=st&3;
 51         st>>=2;
 52     }
 53 }
 54 
 55 int put()
 56 {
 57     memset(v,255,sizeof(v)); v[0]=0;
 58     int t=0,st=0;
 59     for (int i=0; i<n; i++)
 60     {
 61         if (v[b[i]]==-1) v[b[i]]=++t;
 62         st<<=2;
 63         st|=v[b[i]];
 64     }
 65     return st;
 66 }
 67 
 68 bool check(int cur,int nw)
 69 {
 70     get(cur);
 71     int pre=0,k=0,t=n;
 72     for (int i=0; i<n; i++)
 73     {
 74         int x=(nw>>i)&1;
 75         if (pre==0)
 76         {
 77             if (!b[i]&&!x) return 0;
 78             if (b[i]&&x) continue;
 79             if (b[i]) {pre=b[i];b[i]=0;}
 80             else pre=-1;
 81             k=i;
 82         }
 83         else {
 84             if (b[i]&&x) return 0;
 85             if (!b[i]&&!x) continue;
 86             if (b[i])
 87             {
 88                 if (b[i]==pre&&(nw!=0||i!=n-1)) return 0;
 89                 if (pre>0)
 90                 {
 91                     for (int r=0; r<n; r++)
 92                         if (i!=r&&b[r]==b[i]) b[r]=pre;
 93                     b[i]=0;
 94                 }
 95                 else {b[k]=b[i],b[i]=0;}
 96             }
 97             else {
 98                 if (pre>0) b[i]=pre;
 99                 else b[i]=b[k]=++t;
100             }
101             pre=0;
102         }
103     }
104     return pre==0;
105 }
106 
107 void quick(int n)
108 {
109     memset(ans.a,0,sizeof(ans.a));
110     for (int i=1; i<=t; i++) ans.a[i][i]=1;
111     while (n)
112     {
113         if (n&1) ans=ans*c;
114         c=c*c;
115         n>>=1;
116     }
117 }
118 
119 int main()
120 {
121     while (scanf("%d%d",&n,&m)!=EOF)
122     {
123         memset(b,0,sizeof(b));
124         memset(c.a,0,sizeof(c.a));
125         f.clr();
126         f.push(0);
127         b[0]=b[n-1]=1; f.push(put());
128         for (int i=2; i<=f.len; i++)
129             for (int j=0; j<(1<<n); j++)
130                 if (check(f.st[i],j))
131                 {
132                     int k=f.push(put());
133                     c.a[i][k]=1;
134                 }
135         t=f.len;
136         quick(m);
137         if (ans.a[2][1]==0) puts("Impossible");
138         else printf("%d\n",ans.a[2][1]);
139     }
140 }