Contest - ACdream原创群赛の妹子的假期生活 解题报告

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include<math.h>
using namespace std;
const int N = 600;
namespace ufset{int fa[N] , rank[N] , SZ[N];void init(){for (int i = 0 ; i < N ; ++i) SZ[i] = 1 , fa[i] = i , rank[i] = 0;}int findset(int x){int r = x , y ;while(fa[r] != r) r = fa[r];while(fa[x] != r) {y = fa[x] , fa[x] = r , x = y;}return r;}void __unionset(int x , int y){if (rank[x] > rank[y]) {fa[y] = x;SZ[x] += SZ[y];}else {fa[x] = y;SZ[y] += SZ[x];if (rank[x] == rank[y]) ++ rank[y];}}void unionset(int x , int y){int rx = findset(x) , ry = findset(y);if (rx != ry) __unionset(rx , ry);}
}using namespace ufset;
struct Point{double x , y;void input(){scanf("%lf%lf" , &x , &y);}#define sqr(x) ((x) * (x))double dis(const Point & A) const{return sqrt(sqr(x - A.x) + sqr(y - A.y));}
}p[509];
int n , m ;
const double eps = 1e-8;
int dcmp(double d){if (fabs(d) < eps) return 0;return d < 0 ? -1 : 1;
}
struct Rel{int p , q;double nk;bool operator < (const Rel & A) const{return dcmp(nk - A.nk) < 0;}
}relation[509 * 509];
void solve(){scanf("%d%d" , &n,&m);for (int i = 0 ; i < n ; ++i) p[i].input();int rcnt = 0;for (int i = 0 ; i < n ; ++i)for (int j = i + 1 ; j < n ; ++j){relation[rcnt].p = i;relation[rcnt].q = j;relation[rcnt].nk = p[i].dis(p[j]);rcnt++;}sort(relation , relation + rcnt);init();for (int i = 0 ; i < rcnt ; ++i){unionset(relation[i].p , relation[i].q);int rx = findset(relation[i].p) , ry = findset(relation[i].q);if (SZ[rx] >= m || SZ[ry] >= m){printf("%.4lf\n" , relation[i].nk);return;}}
}
int main(){freopen("0.in" , "r" , stdin);freopen("0.out" , "w" , stdout);int T;scanf("%d" , &T);while(T--) solve();
}

G 孟竹的星星

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<vector>
#include<math.h>
using namespace std;
#define fr(i,n) for(int i=0;i<n;i++)
#define fo(i,n) for(int i=1;i<=n;i++)
#define fe(i,n) for(__typeof(n.begin()) i=n.begin();i!=n.end();i++)const double eps=1e-4;const double pi=acos(-1.);struct P{double x,y;P(){}P(double x,double y):x(x),y(y){}void scan(){scanf("%lf %lf",&x,&y);}void print(string s=""){if(s!="")cout << s << ": ";printf("%.2f %.2f\n",x,y);}double dis(const P&a){return hypot(x-a.x,y-a.y);}P rot(double f){double sf=sin(f),cf=cos(f);return P(x*cf-y*sf,y*cf+x*sf);}double dot(const P&a){return x*a.x+y*a.y;}double det(const P&a){return x*a.y-y*a.x;}};bool operator==(const P&a,const P&b){return fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps;}bool operator!=(const P&a,const P&b){return !(a==b);}bool operator<(const P&a,const P&b){if(fabs(a.x-b.x)<eps)return a.y<b.y;return a.x<b.x;}P operator+(const P&a,const P&b){return P(a.x+b.x,a.y+b.y);}P operator-(const P&a,const P&b){return P(a.x-b.x,a.y-b.y);}P operator/(const P&a,double f){return P(a.x/f,a.y/f);}P operator*(const P&a,double f){return P(a.x*f,a.y*f);}int sgn(double x){return x<-eps?-1:x>eps;}namespace triangle{P circumcenter(const P&a,const P&b,const P&c){double x1=a.x,y1=a.y,x2=b.x,y2=b.y,x3=c.x,y3=c.y;double s1=x1*x1+y1*y1,s2=x2*x2+y2*y2,s3=x3*x3+y3*y3;double rx=(y1*(s2-s3)+y2*(s3-s1)+y3*(s1-s2))/(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2));double ry=(x1*(s2-s3)+x2*(s3-s1)+x3*(s1-s2))/(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2));return P(-rx/2,ry/2);}P barycenter(const P&a,const P&b,const P&c){return (a+b+c)/3;}pair<P,double>excircle(const P&a,const P&b,const P&c){P p=circumcenter(a,b,c);return make_pair(p,p.dis(a));}}
int main()
{int t,ss;P a,b,c,d,e,w,r,p[5],s[3];for(scanf("%d",&t);t--;){a.scan();b.scan();c.scan();w=triangle::circumcenter(a,b,c);r=w-a;ss=0;p[0]=a;for(int i=1;i<5;i++)p[i]=(p[i-1]-w).rot(2*pi/5)+w;for(int i=0;i<5;i++)if(p[i]!=a&&p[i]!=b&&p[i]!=c)s[ss++]=p[i];sort(s,s+ss);for(int i=0;i<2;i++)s[i].print();}return 0;
}

const int head=0;
//const int INF=10000000;
const int maxn = 610;
const int maxd = 1000000;
int N, M, K,  cnt, res;
int mat[maxn][maxn], s[maxn], l[maxd], r[maxd], u[maxd], d[maxd], c[maxd], o[maxn], row[maxd];
bool use[maxn];
void makegragh(int &n, int &m)
{memset(mat, 0, sizeof(mat));
//初始化mat矩阵
}
void initial(int n, int m)
{memset(use, false, sizeof(use));res=n+1;int i, j, rowh;memset(s, 0, sizeof(s));for(i=head; i<=m; i++){r[i]=(i+1)%(m+1);l[i]=(i-1+m+1)%(m+1);u[i]=d[i]=i;}cnt=m+1;for(i=1; i<=n; i++){rowh=-1;for(j=1; j<=m; j++){//printf("%d", mat[i][j]);if(mat[i][j]){s[j]++;u[cnt]=u[j];d[u[j]]=cnt;u[j]=cnt;d[cnt]=j;row[cnt]=i;c[cnt]=j;if(rowh==-1){l[cnt]=r[cnt]=cnt;rowh=cnt;}else{l[cnt]=l[rowh];r[l[rowh]]=cnt;r[cnt]=rowh;l[rowh]=cnt;}cnt++;}}//puts("");}
}
void remove(int c)
{for(int i=d[c]; i!=c; i=d[i]){r[l[i]]=r[i];l[r[i]]=l[i];}
}
void resume(int c)
{for(int i=d[c]; i!=c; i=d[i])r[l[i]]=l[r[i]]=i;
}
int h()
{bool has[maxn];memset(has, false, sizeof(has));int ans=0;for(int i=r[head]; i!=head; i=r[i])if(!has[i]){ans++;for(int j=d[i]; j!=i; j=d[j])for(int k=r[j]; k!=j; k=r[k])has[c[k]]=true;}return ans;
}
int marrige[maxn];
bool dfs(int k)
{if(k+h()>=res)return false;//A* cutif(r[head]==head){if(k<res) res=k;return true;}int ms=INF, cur=0;for(int t=r[head]; t!=head; t=r[t])if(s[t]<ms){ms=s[t];cur=t;}for(int i=d[cur]; i!=cur; i=d[i]){int rr = row[i];if (marrige[rr] == 0 || use[marrige[rr]] == 0) use[rr] = 1;else continue;
//        int rr = (row[i] - 1) / 2 + 1;
//        if (!use[rr]) use[rr] = true;
//        else continue;remove(i);for(int j=r[i]; j!=i; j=r[j]){remove(j);s[c[j]]--;}dfs(k+1);for(int j=l[i]; j!=i; j=l[j]){resume(j);s[c[j]]++;}use[rr] = false;resume(i);}return false;
}
int n , m;
int P , x , y;
VI edge[maxn];
void vdfs(int now , int x){mat[x][now] = 1;ECH(it , edge[now]){int go = *it;if (!mat[x][go]) vdfs(go , x);}
}
void solve(){RST(marrige);RST(mat);RD(n , m);
//    printf("%d %d :" , n , m);for (int i = 1 ; i <= n + m ; ++i) edge[i].clear();for (int i = 1 ; i <= n + m ; ++i)edge[i].PB(i);RD(P);DO(P){RD(x , y);//mat[x][n + y] = 1;edge[x].PB(n + y);}RD(P);DO(P){RD(x , y);//mat[n + x][y] = 1;edge[n + x].PB(y);}RD(P);DO(P){RD(x , y);marrige[x] = y + n;marrige[y + n] = x;}for(int i = 1 ; i <= n + m ; ++i){vdfs(i , i);}
//    for (int i = 1 ; i <= n + m ; ++i){
//        for (int j = 1 ; j <= n + m ; ++j)
//            printf("%d " , mat[i][j]);
//        cout << endl;
//    }initial(n + m , n + m);
//    cout << "DS" << endl;dfs(0);cout << res << endl;
}
int main(){freopen("0.in" , "r" , stdin);freopen("0.out" , "w" , stdout);Rush solve();
}

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
using namespace std;
#define fr(i,n) for(int i=0;i<n;i++)
#define fo(i,n) for(int i=1;i<=n;i++)
#define fe(i,n) for(__typeof(n.begin()) i=n.begin();i!=n.end();i++)
int t,n,m,p,q,w,scc,x,y,in[2020];
int low[2020],dfn[2020],cnt;
int v[2020],r[2020],s[2020],ss;
int f[2020],z;
vector<int>a[2020];
set<int>se[2020];
int dfs(int x)
{dfn[x]=low[x]=++cnt;s[ss++]=x;v[x]=1;fe(i,a[x]){if(!dfn[*i]){dfs(*i);low[x]=min(low[x],low[*i]);}else if(v[*i]){low[x]=min(low[x],dfn[*i]);}}if(dfn[x]==low[x]){scc++;do{v[s[ss-1]]=0;r[s[ss-1]]=scc;se[scc].insert(s[ss-1]);
//          c[scc]++;}while(s[--ss]!=x);}return 0;
}
int main()
{for(scanf("%d",&t);t--;){scc=0;cnt=0;z=0;memset(in,0,sizeof in);memset(f,0,sizeof f);memset(low,0,sizeof low);memset(dfn,0,sizeof dfn);memset(v,0,sizeof v);memset(r,0,sizeof r);scanf("%d%d",&n,&m);for(int i=1;i<=m+n;i++)a[i].clear();for(int i=1;i<=m+n;i++)se[i].clear();scanf("%d",&p);for(int i=0;i<p;i++){scanf("%d%d",&x,&y);a[x].push_back(y+n);}scanf("%d",&q);for(int i=0;i<q;i++){scanf("%d%d",&x,&y);a[x+n].push_back(y);}scanf("%d",&w);for(int i=0;i<w;i++){scanf("%d%d",&x,&y);f[x]=y+n;f[y+n]=x;}for(int i=1;i<=m+n;i++)if(!dfn[i])dfs(i);queue<int>q;for(int i=1;i<=m+n;i++)fe(j,a[i])if(r[i]!=r[*j])in[r[*j]]++;for(int i=1;i<=m+n;i++)if(se[r[i]].size()==1&&in[r[i]]==0)q.push(i);for(int i=1;i<=scc;i++)if(in[i]==0)z++;while(q.size()){int u=q.front();q.pop();if(f[u]&&in[r[f[u]]]==0){se[r[f[u]]].erase(f[u]);if(se[r[f[u]]].size()==0){printf("%d\n",n+m+1);goto end;}else if(se[r[f[u]]].size()==1){q.push(*se[r[f[u]]].begin());}}}printf("%d\n",z);end:;}
}

typedef long long int64;struct Int {int x;Int() :x(0) {}Int(int _x) :x(_x) {x %= MOD;if (x < 0)x += MOD;}Int(int64 _x) {x = _x % MOD;if (x < 0)x += MOD;}static Int get(int x) {Int a;a.x = x;return a;}Int operator+(const Int&o) const {int t = x + o.x;if (t >= MOD)t -= MOD;return get(t);}Int operator*(const Int&o) const {return get(1LL * x * o.x % MOD);}Int operator-(const Int&o) const {int t = x - o.x;if (t < 0)t += MOD;return get(t);}Int operator/(const Int&o) const {return (*this) * o.inv();}Int&operator+=(const Int&o) {return (*this) = *this + o;}Int&operator-=(const Int&o) {return (*this) = *this - o;}Int&operator*=(const Int&o) {return (*this) = *this * o;}Int&operator/=(const Int&o) {return (*this) = *this / o;}Int power(int64 n) const {if (!n)return get(1);const Int&a = *this;if (n & 1)return power(n - 1) * a;elsereturn (a * a).power(n >> 1);}Int inv() const {return power(MOD - 2);}
};/* .................................................................................................................................. */
Int D(Int n){Int ret;ret = n * (n + 1) / 2;ret = ret + 1;return ret;
}
void solve(){char op[2];Int n , ans;scanf("%s%d" , op , &n.x);if (op[0] == 'L'){ans = D(n);//cout << ans.x << endl;OT(ans.x);}else if (op[0] == 'V'){ans = D(n * 2);ans = ans - n * 2;//cout << ans.x << endl;OT(ans.x);}else if (op[0] == 'Z'){ans = D(n * 3);ans = ans - n * 5;//cout << ans.x << endl;OT(ans.x);}
}
int main(){freopen("0.in" , "r" , stdin);freopen("0.out" , "w" , stdout);Rush solve();
}

#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<queue>
#define inf 1000000005
#define M 40
#define N 100005
#define maxn 300005
#define eps 1e-12
#define zero(a) fabs(a)<eps
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define MOD 1000000009
#define lson step<<1
#define rson step<<1|1
#define sqr(a) ((a)*(a))
#define Key_value ch[ch[root][1]][0]
#define test puts("OK");
#define pi acos(-1.0)
#define lowbit(x) ((-(x))&(x))
#define HASH1 1331
#define HASH2 10001
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
LL a,b,c;
int main(){//freopen("input.txt","r",stdin);int  t;char str[10];cin>>t;while(t--){scanf("%s%d" , str , &a);LL ans;if(str[0]=='L') ans=(a*(a+1)/2 + 1)%MOD;else if(str[0]=='V') ans=(2*a*(2*a+1)/2+1-2*a)%MOD;else ans=(3*a*(3*a+1)/2+1-5*a)%MOD;cout<<ans<<endl;}return 0;
}

const int MATN = 129;
const LL modo = MOD;
struct Mat{int Matn , Matm;LL a[MATN][MATN];Mat(){Matn = 0;Matm = 0;memset(a , 0 , sizeof(a));}void output(){cout << "OUTPUT" << endl;for (int i = 0 ; i < Matn ; ++i){for (int j = 0 ; j < Matm ; ++j){printf("%lld ",a[i][j]);}printf("\n");}}void init(){Matn = 0;Matm = 0;memset(a , 0 , sizeof(a));}Mat operator + (const Mat & A) const{Mat ret = A;for (int i = 0 ; i < Matn ; ++i){for (int j = 0 ; j < Matm ; ++j)ret.a[i][j] = (ret.a[i][j] + a[i][j]) % modo;}return ret;}Mat operator * (const Mat & A) const{Mat c ;c.Matn = Matn;c.Matm = A.Matm;for (int i = 0 ; i < Matn ; ++i)for (int j = 0 ; j < A.Matm ; ++j)for (int k = 0 ; k < Matm ; ++k)c.a[i][j] = (c.a[i][j] + (a[i][k] * A.a[k][j])%modo)%modo;return c;}void initI(){memset(a, 0 , sizeof(a));for (int i = 0 ; i < Matn ; ++i)a[i][i] = 1;}Mat power(LL k){Mat c = *this  , b;b.init();b.Matn = Matn ; b.Matm = Matm;b.initI();while(k){if (k & 1LL)b = b * c;c = c * c;k >>= 1LL;}return b;}
}QQ;
struct ZHU{Mat a[2][2];void init(const Mat& p){for (int i = 0 ; i < 2 ; ++i)for (int j=  0 ; j < 2 ;++j){a[i][j].init();a[i][j].Matn = 128 ; a[i][j].Matm = 128;}a[0][0] = p;a[0][1].initI();a[1][1].initI();}void initI(){for (int i = 0 ; i < 2 ; ++i)for (int j=  0 ; j < 2 ;++j){a[i][j].Matn = 128 ; a[i][j].Matm = 128;a[i][i].initI();}}ZHU operator * (const ZHU & A) const{ZHU res;for (int i = 0 ; i < 2 ; ++i)for (int j= 0 ; j < 2 ;++j){res.a[i][j].init();res.a[i][j].Matn = 128 ; res.a[i][j].Matm = 128;}for (int i = 0 ; i < 2 ; ++i)for (int j = 0 ; j < 2 ; ++j)for (int k = 0 ; k < 2 ; ++k)res.a[i][j] = (res.a[i][j] + a[i][k] * A.a[k][j]);return res;}void copy(const ZHU & A) {for(int i = 0 ; i < 2 ; ++i)for (int j = 0 ; j < 2 ; ++j)a[i][j] = A.a[i][j];}Mat power(LL k);
}R , nR , b , c;
Mat ZHU::power(LL k){
//    printf("\nINT ");
//    cout << k << endl;c = *this;bool f = false;while(k){if (k & 1LL){if (!f) b = c;else b = b * c;f = true;}c = c * c;k >>= 1LL;}if (!f){b = c;b.a[0][1].initI();}return b.a[0][1];
}
const int PCODE[] = {0 , 1 , 2 , 4 , 8 , 16 , 32 , 64 , 0};
struct Under{bool mp[3][3];int hash;int encode(){hash = 0;for (int i = 0 ; i < 3 ; ++i)for(int j = 0 ; j < 3 ; ++j)if (mp[i][j])hash |= PCODE[i * 3 + j];return hash;}void decode(){RST(mp);for (int i = 0 ; i < 3 ; ++i)for(int j = 0 ; j < 3 ; ++j){if (i + j == 0 || i + j == 4) continue;if (hash & (PCODE[i * 3 + j]))mp[i][j] = true;else mp[i][j] = false;}}void output(){printf("  %d %d\n", mp[0][1] , mp[0][2]);printf("%d %d %d\n" , mp[1][0] , mp[1][1] , mp[1][2]);printf("%d %d\n", mp[2][0] , mp[2][1]);}void input(){for(int i = 0 ; i < 3 ; ++i)for (int j = 0 ; j < 3 ; ++j){if (i + j == 0 || i + j == 4) continue;int x;RD(x);mp[i][j] = x;}encode();}}en , temp;
LL n;
Mat P , Q ;
void solve(){RD(n);en.input();Mat nP = P;
//    nP.output();nR.copy(R);
//    nR.a[0][1].output();
//    printf("N %lld\n" , n);QQ = nR.power(n);
//    cout << "DS" << endl;nP = nP * QQ;printf("%lld\n" , nP.a[0][en.hash]);
}
bool inmap(int x , int y){if (x + y == 0) return false;if (x + y == 4) return false;return 0 <= x && x < 3 && 0 <= y && y < 3;
}
int canput(int bi , int x , int y , int d){temp.hash = bi;temp.decode();if (!inmap(x , y) || !inmap(x + dx4[d] , y + dy4[d]) || !inmap(x + dx4[(d + 1) % 4] , y + dy4[(d + 1) % 4])) return -1;if (!temp.mp[x][y] || !temp.mp[x + dx4[d]][y + dy4[d]] || !temp.mp[x + dx4[(d + 1) % 4]][y + dy4[(d + 1) % 4]]) return -1;temp.mp[x][y] = 0;temp.mp[x + dx4[d]][y + dy4[d]] = 0;temp.mp[x + dx4[(d + 1) % 4]][y + dy4[(d + 1) % 4]] = 0;return temp.encode();
}
int takeOut(int bi , int x , int y , int d){temp.hash = bi;temp.decode();temp.mp[x][y] = 0;temp.mp[x + dx4[d]][y + dy4[d]] = 0;temp.mp[x + dx4[(d + 1) % 4]][y + dy4[(d + 1) % 4]] = 0;return temp.encode();
}
bool canput2(int bi , int x , int y , int d , int x1 , int y1 , int d1){temp.hash = bi;temp.decode();if (!inmap(x , y) || !inmap(x + dx4[d] , y + dy4[d]) || !inmap(x + dx4[(d + 1) % 4] , y + dy4[(d + 1) % 4])) return false;if (!temp.mp[x][y] || !temp.mp[x + dx4[d]][y + dy4[d]] || ! temp.mp[x + dx4[(d + 1) % 4]][y + dy4[(d + 1) % 4]]) return false;temp.mp[x][y] = 0;temp.mp[x + dx4[d]][y + dy4[d]] = 0;temp.mp[x + dx4[(d + 1) % 4]][y + dy4[(d + 1) % 4]] = 0;if (!inmap(x1 , y1) || !inmap(x1 + dx4[d1] , y1+ dy4[d1]) || !inmap(x1 + dx4[(d1 + 1) % 4] , y1 + dy4[(d1 + 1) % 4])) return false;if (!temp.mp[x1][y1] || !temp.mp[x1 + dx4[d1]][y1 + dy4[d1]] || ! temp.mp[x1 + dx4[(d1 + 1) % 4]][y1 + dy4[(d1 + 1) % 4]]) return false;temp.mp[x1][y1] = 0;temp.mp[x1 + dx4[d1]][y1 + dy4[d1]] = 0;temp.mp[x1 + dx4[(d1 + 1) % 4]][y1 + dy4[(d1 + 1) % 4]] = 0;return temp.encode() == 0;}
void initialP(){P.init();P.Matn = 1 , P.Matm = 128;for (int i = 0 ; i < 128 ; ++i)for (int j = 0 ; j < 3 ; ++j)for (int k = 0 ; k < 3 ; ++k)for (int d = 0 ; d < 4 ; ++d){int res = canput(i , j , k , d);if (res == 0)++P.a[0][i];}for (int i = 0 ; i < 128 ; ++i)for (int j = 0 ; j < 3 ; ++j)for (int k = 0 ; k < 3 ; ++k)for (int d = 0 ; d < 4 ; ++d)for (int j1 = i ; j1 < 3 ; ++j1)for (int k1 = j ; k1 < 3 ; ++k1)for (int d1 = 0 ; d1 < 4 ; ++d1){bool res = (canput2(i , j , k , d , j1 , k1 , d1));if (res)++P.a[0][i];}
//    for (int i = 0 ; i < 128 ; ++i)
//    if (P.a[0][i] == 2){
//        temp.hash = i;
//        temp.decode();
//        temp.output();
//    }
}
vector< PII > memory[129][129];
bool has(int bi , int bb){int res = bi & bb;return res == bb;
}
int ok[129][129];
bool canPush(int down , int up){
//    printf("PRE : %d %d\n" , down , up);if(down + up == 0) {ok[down][up] = 1;return 1;}
//    printf("%d\n" , ok[down][up]);if (ok[down][up] != -1) return ok[down][up];//    printf("NEX : %d %d\n" , down , up);//if (memory[down][up] != -1) return memory[down][up];for (int i = 0 ; i < 3 ; ++i)for (int j = 0 ; j < 3 ; ++j)for (int d = 0 ; d < 4 ; ++d){int res = canput(down , i , j , d);if (res != -1){int newdown = res;if (canPush(newdown , up)){memory[down][up].PB(MP(newdown , up));//return 1;}}}for (int i = 0 ; i < 3 ; ++i)for (int j = 0 ; j < 3 ; ++j)for (int d = 0 ; d < 4 ; ++d){int res = canput(up , i , j , d);if (res != -1){int newup = res;if (canPush(down , newup)){memory[down][up].PB(MP(down , newup));
//                return 1;}}}/**1   24   8   1632  64*/if (has(down , 3) && has(up , 1))if (canPush(down - 3 , up - 1)){memory[down][up].PB(MP(down - 3 , up - 1));}// = 1 ; return 1;}if (has(down , 3) && has(up , 2))if (canPush(down - 3 , up - 2)){memory[down][up].PB(MP(down - 3 , up - 2));}// = 1 ; return 1;}if (has(down , 12) && has(up , 4))if (canPush(down - 12 , up - 4)){memory[down][up].PB(MP(down - 12 , up - 4));}// = 1 ; return 1;}if (has(down , 12) && has(up , 8))if (canPush(down - 12 , up - 8)){memory[down][up].PB(MP(down - 12 , up - 8));}// = 1 ; return 1;}if (has(down , 24) && has(up , 8))if (canPush(down - 24 , up - 8)){memory[down][up].PB(MP(down - 24 , up - 8));}// = 1 ; return 1;}if (has(down , 24) && has(up , 16))if (canPush(down - 24 , up - 16)){memory[down][up].PB(MP(down - 24 , up - 16));}// = 1 ; return 1;}if (has(down , 96) && has(up , 32))if (canPush(down - 96 , up - 32)){memory[down][up].PB(MP(down - 96 , up - 32));}// = 1 ; return 1;}if (has(down , 96) && has(up , 64))if (canPush(down - 96 , up - 64)){memory[down][up].PB(MP(down - 96 , up - 24));}// = 1 ; return 1;}/**1   24   8   1632  64*/if (has(down , 36) && has(up , 4))if (canPush(down - 36 , up - 4)){memory[down][up].PB(MP(down - 36 , up - 4));}// = 1 ; return 1;}if (has(down , 36) && has(up , 32))if (canPush(down - 36 , up - 32)){memory[down][up].PB(MP(down - 36 , up - 32));}// = 1 ; return 1;}if (has(down , 9) && has(up , 1))if (canPush(down - 9 , up - 1)){memory[down][up].PB(MP(down - 9 , up - 1));}// = 1 ; return 1;}if (has(down , 9) && has(up , 8))if (canPush(down - 9 , up - 8)){memory[down][up].PB(MP(down - 9 , up - 8));}// = 1 ; return 1;}if (has(down , 72) && has(up , 8))if (canPush(down - 72 , up - 8)){memory[down][up].PB(MP(down - 72 , up - 8));}// = 1 ; return 1;}if (has(down , 72) && has(up , 64))if (canPush(down - 72 , up - 64)){memory[down][up].PB(MP(down - 72 , up - 64));}// = 1 ; return 1;}if (has(down , 18) && has(up , 2))if (canPush(down - 18 , up - 2)){memory[down][up].PB(MP(down - 18 , up - 2));}// = 1 ; return 1;}if (has(down , 18) && has(up , 16))if (canPush(down - 18 , up - 16)){memory[down][up].PB(MP(down - 18 , up - 16));}// = 1 ; return 1;}/**1   24   8   1632  64*/if (has(up , 3) && has(down , 1))if (canPush(down - 1 , up - 3 )){memory[down][up].PB(MP(down - 1 , up - 3));}// = 1 ; return 1;}if (has(up , 3) && has(down , 2))if (canPush(down - 2 , up - 3)){memory[down][up].PB(MP(down - 2 , up - 3));}// = 1 ; return 1;}if (has(up , 12) && has(down , 4))if (canPush(down - 4 , up - 12)){memory[down][up].PB(MP(down - 4 , up - 12));}// = 1 ; return 1;}if (has(up , 12) && has(down , 8))if (canPush(down - 8 , up - 12)){memory[down][up].PB(MP(down - 8 , up - 12));}// = 1 ; return 1;}if (has(up , 24) && has(down , 8))if (canPush(down - 8 , up - 24)){memory[down][up].PB(MP(down - 8 , up - 24));}// = 1 ; return 1;}if (has(up , 24) && has(down , 16))if (canPush(down - 16 , up - 24)){memory[down][up].PB(MP(down - 16 , up - 24));}// = 1 ; return 1;}if (has(up , 96) && has(down , 32))if (canPush(down - 32 , up - 96)){memory[down][up].PB(MP(down - 32 , up - 96));}// = 1 ; return 1;}if (has(up , 96) && has(down , 64))if (canPush(down - 64 , up - 96)){memory[down][up].PB(MP(down - 64 , up - 96));}// = 1 ; return 1;}/**1   24   8   1632  64*/if (has(up , 36) && has(down , 4))if (canPush(down - 4 , up - 36)){memory[down][up].PB(MP(down - 4 , up - 36));}// = 1 ; return 1;}if (has(up , 36) && has(down , 32))if (canPush(down - 32 , up - 36)){memory[down][up].PB(MP(down - 32 , up - 36));}// = 1 ; return 1;}if (has(up , 9) && has(down , 1))if (canPush(down - 1 , up - 9)){memory[down][up].PB(MP(down - 1 , up - 9));}// = 1 ; return 1;}if (has(up , 9) && has(down , 8))if (canPush(down - 8 , up - 9)){memory[down][up].PB(MP(down - 8 , up - 9));}// = 1 ; return 1;}if (has(up , 72) && has(down , 8))if (canPush(down - 8 , up - 72)){memory[down][up].PB(MP(down - 8 , up - 72));}// = 1 ; return 1;}if (has(up , 72) && has(down , 64))if (canPush(down - 64 , up - 72)){memory[down][up].PB(MP(down - 64 , up - 72));}// = 1 ; return 1;}if (has(up , 18) && has(down , 2))if (canPush(down - 2 , up - 18)){memory[down][up].PB(MP(down - 2 , up - 18));}// = 1 ; return 1;}if (has(up , 18) && has(down , 16))if (canPush(down - 16 , up - 18)){memory[down][up].PB(MP(down - 16 , up - 18));}// = 1 ; return 1;}ok[down][up] = (SZ(memory[down][up]) > 0);return SZ(memory[down][up]) > 0;
}
vector<PII> cmp1 , cmp2;
struct ME{vector<PII> del;ME(){del.clear();}void rush(){sort(ALL(del));}bool operator < (const ME & A) const{cmp1 = del;cmp2 = A.del;sort(ALL(cmp1));sort(ALL(cmp2));//if (SZ(cmp1) != SZ(cmp2)) return SZ(cmp1) < SZ(cmp2);for (int i = 0 ; i < min(SZ(cmp1) , SZ(cmp2)) ; ++i)if (cmp1[i] != cmp2[i])return cmp1[i] < cmp2[i];return false;}bool operator == (const ME & A) const{return (!(*this < A) && !(A < *this));}
};
vector<ME> mycnt;
vector<PII> :: iterator iter;
ME now;
void cnt(int down , int up){
//    printf("PRE %d %d\n" , down , up);if(down == 0 && up == 0){mycnt.PB(now);return;}if (ok[down][up] == 0) return;
//    printf("CNT: %d %d\n" , down , up);
//    cout << SZ(memory[down][up]) << endl;for(int i = 0 ; i < SZ(memory[down][up]) ;++i){int newdown = memory[down][up][i].fi;int newup = memory[down][up][i].se;
//        printf("-%d %d\n", newdown , newup);now.del.PB( MP(down - newdown , up - newup) );
//        printf("+ %d %d\n" , down - newdown , up - newup);cnt(newdown , newup);iter = now.del.end() - 1;//iter--;
//        printf("- %d %d\n" , iter->fi , iter->se);now.del.erase(iter);//( MP(down - newdown , up - newup) );}
}
void initialQ(){Q.init();Q.Matn = 128 , Q.Matm = 128;
//    canPush(3 , 127);mycnt.clear();
//    cnt(3 , 127);
//    sort(ALL(mycnt));
//    printf("%d\n" , unique(ALL(mycnt)) - mycnt.begin());return;
//    for (int i = 0 ; i < 128 ; ++i)
//        for (int j = 0 ; j < 128; ++j)
//            canPush(i , j);for (int i = 0 ; i < 128 ; ++i)for (int j = 0 ; j < 128 ; ++j){if (canPush(127 - j , i)){mycnt.clear();cnt(127 - j , i);sort( ALL(mycnt) );Q.a[j][i] = unique(ALL(mycnt)) - mycnt.begin();
//
//                printf("<<<<<<<<<<<\n");
//                temp.hash = j;printf("%d:\n" , j);temp.decode();temp.output();
//                temp.hash = i;printf("%d:\n" , i);temp.decode();temp.output();
//                printf(">>>>>>>>>>>\n");
//                printf("%d\n" , SZ(mycnt));
//                for (int ds = 0 ; ds < SZ(mycnt) ; ++ds){
//                    for (int Meng = 0 ; Meng < mycnt[ds].del.size() ; ++Meng)
//                        printf("(%d,%d)  " , mycnt[ds].del[Meng].fi , mycnt[ds].del[Meng].se);
//                    cout << endl;
//                }
//                cout << endl;
//                printf("%d\n" , Q.a[j][i]);}else Q.a[j][i] = 0;}
}
void initialR(){R.init(Q);
}
void init(){memset(ok , -1 , sizeof(ok));for (int i = 0 ; i < 128 ; ++i)for (int j = 0 ; j < 128 ; ++j)memory[i][j].clear();initialP();initialQ();initialR();
//    cout << "GG" << endl;
}
int main(){
//    freopen("0.in" , "r" , stdin);
//    freopen("1.out" , "w" , stdout);init();solve();
}

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<vector>
using namespace std;
#define fr(i,n) for(int i=0;i<n;i++)
#define fo(i,n) for(int i=1;i<=n;i++)
#define fe(i,n) for(__typeof(n.begin()) i=n.begin();i!=n.end();i++)
int a[100020],ac;
int v[100020];
long long A[130][130];
long long B[130][130];
int N=1<<7,p=1000000007;
int mk(int x,int y,int z)
{return 1<<x|1<<y|1<<z;
}
void pre()
{int x[]={0,0,1,1,1,2,2};int y[]={1,2,0,1,2,0,1};int r[3][3]={-1,0,1,2,3,4,5,6,-1};int u[3][3]={-1,7,8,9,10,11,12,13,-1};int dx[]={1,0,-1,0};int dy[]={0,1,0,-1};for(int i=0;i<7;i++){int nx=x[i],ny=y[i];for(int i=0;i<4;i++){int qx=nx+dx[i];int qy=ny+dy[i];if(qx>=0&&qy>=0&&qx<3&&qy<3&&r[qx][qy]!=-1){a[ac++]=mk(r[nx][ny],u[nx][ny],r[qx][qy]);a[ac++]=mk(r[nx][ny],u[nx][ny],u[qx][qy]);}int px=nx+dx[i+1&3];int py=ny+dy[i+1&3];if(qx>=0&&qy>=0&&qx<3&&qy<3&&r[qx][qy]!=-1)if(px>=0&&py>=0&&px<3&&py<3&&r[px][py]!=-1){a[ac++]=mk(r[nx][ny],r[px][py],r[qx][qy]);
//                  a[ac++]=mk(u[nx][ny],u[px][py],u[qx][qy]);}                   }}
}
void mul(long long a[130][130],long long b[130][130],long long c[130][130])
{long long r[130][130]={};for(int i=0;i<N;i++)for(int k=0;k<N;k++)if(a[i][k])for(int j=0;j<N;j++)r[i][j]=(r[i][j]+a[i][k]*b[k][j])%p;for(int i=0;i<N;i++)for(int j=0;j<N;j++)c[i][j]=r[i][j];
}
int main()
{N++; pre();
//  cout << ac << endl;v[0]=1;for(int j=0;j<ac;j++)for(int i=0;i<1<<14;i++)if(v[i])if((i&a[j])==0)v[i|a[j]]++;int t,n;for(;~scanf("%d",&n);){memset(A,0,sizeof A);memset(B,0,sizeof B);A[0][0]=1;for(int i=0;i<N-1;i++)for(int j=0;j<N-1;j++)B[i][j]=v[i<<7|(127^j)];n++;int w=0;for(int i=0;i<7;i++){int d;scanf("%1d",&d);w=w*2+1-d;}B[w][N-1]=1;B[N-1][N-1]=1;for(;n;n>>=1){if(n&1)mul(A,B,A);mul(B,B,B);}if(A[0][N-1]==0)puts("No way");elseprintf("%d\n",(int)A[0][N-1]);}return 0;
}

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <cmath>using namespace std;#ifndef ONLINE_JUDGE
#define DEBUG(a) cout << #a"= " << a << endl
#else
#define DEBUG(a)
#endif
typedef long long LL;
const int maxn = 1 << 7;
const int mod = (int)1e9 + 7;struct Martix {LL C[maxn][maxn];Martix() { memset(C, 0, sizeof(C)); }void init() { memset(C, 0, sizeof(C)); }void initC() { for (int i = 0; i < maxn; ++i) C[i][i] = 1; }Martix operator*(const Martix& rhs) const {Martix res;for (int i = 0; i < maxn; ++i) {for (int j = 0; j < maxn; ++j) {for (int k = 0; k < maxn; ++k) {res.C[i][j] += C[i][k] * rhs.C[k][j];res.C[i][j] %= mod;}}}return res;}Martix operator+(const Martix& rhs) const {Martix res;for (int i = 0; i < maxn; ++i) {for (int j = 0; j < maxn; ++j) {res.C[i][j] = C[i][j] + rhs.C[i][j];if (res.C[i][j] >= mod) res.C[i][j] -= mod;}}return res;}
};Martix start, inc;
int Kr[8][4] = {{3, 9}, {3, 6}, {6, 12}, {9, 12, 24, 72},{24, 48}, {48, 96}, {72, 96}
};
int Sr[] = {7, 11, 13, 14, 25, 56, 76, 88, 104, 112
};
void dfs(int deep, int s, int ps) {if (deep == 17) {++start.C[ps^(maxn - 1)][s ^ (maxn - 1)]; return;}if (deep < 7) {int sz = (deep == 3) ? 4 : 2;for (int i = 0; i < sz; ++i) {if ((s & Kr[deep][i]) == Kr[deep][i])dfs(deep + 1, s ^ Kr[deep][i], ps ^ (1 << deep));}dfs(deep + 1, s, ps);} else {if ((s & Sr[deep - 7]) == Sr[deep - 7]) dfs(deep + 1, s ^ Sr[deep - 7], ps);dfs(deep + 1, s, ps);}
}Martix powMartix(Martix base, int N) {Martix res; res.initC();while (N) {if (N & 1) res = res * base;base = base * base;N >>= 1;}return res;
}Martix sumMartix(int N) {if (N == 0) {return inc;} else if (N == 1) {return start;} else if (N % 2 == 0) {Martix tmp = powMartix(start, N >> 1);tmp = tmp + inc;return tmp * sumMartix(N >> 1);} else {Martix tmp = powMartix(start, N);return tmp + sumMartix(N - 1);}
}void solved(int nT) {char s[12]; int N;scanf("%d", &N);int rs = 0;scanf("%s", s);if (s[0] == '1') rs |= 1;if (s[1] == '1') rs |= 2;scanf("%s", s);if (s[0] == '1') rs |= 16;if (s[1] == '1') rs |= 8;if (s[2] == '1') rs |= 4;scanf("%s", s);if (s[0] == '1') rs |= 32;if (s[1] == '1') rs |= 64;Martix result = sumMartix(N);LL res = result.C[maxn - 1][rs];if (res == 0) puts("No way");else printf("%lld\n", res);
}int main() {dfs(0, maxn - 1, 0);inc.initC();int T = 1;//scanf("%d", &T);for (int nT = 1; nT <= T; ++nT) {solved(nT);}return 0;
}

#include <iostream>
#include <fstream>
#include <string.h>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <cassert>
#include <iomanip>
#include <math.h>
#include <deque>
#include <utility>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <climits>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <sstream>using namespace std;typedef unsigned long long ull;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <double, double> pdd;
typedef vector <int> vi;
typedef vector <ll> vl;
typedef vector <double> vd;
typedef vector <string> vs;
typedef map <string, int> mpsi;
typedef map <double, int> mpdi;
typedef map <int, int> mpii;const double pi = acos(0.0) * 2.0;
const double eps = 1e-12;
const int step[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};template <class T> inline T abs1(T a) {return a < 0 ? -a : a;}
template <class T> inline T max1(T a, T b) {return a > b ? a : b;}
template <class T> inline T min1(T a, T b) {return a < b ? a : b;}
template <class T> inline T gcd1(T a, T b) {if(a < b) swap(a, b);if(a % b == 0) return b;return gcd1(b, a % b);
}
template <class T> inline T lb(T num) {return num & (-num); }
inline int jud(double a, double b){if(abs1(a - b) < eps) return 0;if(a < b) return -1;return 1;
}
template <class t>
inline int find(int val, t *a, int na, bool f_small = 1, bool f_lb = 1){if(na == 1) return 0;int be = 0, en = na - 1;if(a[0] <= a[na - 1]){if(f_lb == 0) while(be < en){int mid = (be + en + 1) / 2;if(jud(a[mid], val) != 1) be = mid;else en = mid - 1;}else while(be < en){int mid = (be + en) / 2;if(jud(a[mid], val) != -1) en = mid;else be = mid + 1;}if(f_small && a[be] > val && be != 0) be--;if(!f_small && a[be] < val && be != na - 1) be++;} else {if(f_lb) while(be < en){int mid = (be + en + 1) / 2;if(jud(a[mid], val) != -1) be = mid;else en = mid - 1;}else while(be < en){int mid = (be + en) / 2;if(jud(a[mid], val) != 1) en = mid;else be = mid + 1;}if(!f_small && a[be] < val && be != 0) be--;if(f_small && a[be] > val && be != na - 1) be++;}return be;
}
inline int bitnum(ull nValue){nValue = ((0xaaaaaaaaaaaaaaaaull & nValue)>>1) + (0x5555555555555555ull & nValue);nValue = ((0xccccccccccccccccull & nValue)>>2) + (0x3333333333333333ull & nValue);nValue = ((0xf0f0f0f0f0f0f0f0ull & nValue)>>4) + (0x0f0f0f0f0f0f0f0full & nValue);nValue = ((0xff00ff00ff00ff00ull & nValue)>>8) + (0x00ff00ff00ff00ffull & nValue);nValue = ((0xffff0000ffff0000ull & nValue)>>16) + (0x0000ffff0000ffffull & nValue);nValue = ((0xffffffff00000000ull & nValue)>>32) + (0x00000000ffffffffull & nValue);return nValue;
}
long long pow(long long n, long long m, long long mod = 0){long long ans = 1;long long k = n;while(m){if(m & 1) {ans *= k;if(mod) ans %= mod;}k *= k;if(mod) k %= mod;m >>= 1;}return ans;
}const int mod = 1000000007;
template <typename t> struct matrix{const static int maxn = 130;int row, col;t mat[maxn][maxn];matrix(int r = 0, int c = 0){row = r; col = c;for(int i = 0; i < row; i++) for(int j = 0; j < col; j++) mat[i][j] = 0;}bool danweiju(){if(row != col) return 0;for(int i = 0; i < row; i++) for(int j = 0; j < col; j++) mat[i][j] = bool (i == j);return 1;}matrix operator * (const matrix& b) const{int i, j, k;matrix <t> c(row, b.col);memset(c.mat, 0, sizeof(c.mat));for (i = 0; i < c.row; i++) for (k = 0; k < col; k++)if(mat[i][k])for (j = 0; j < c.col; j++){c.mat[i][j] += mat[i][k] * b.mat[k][j];c.mat[i][j] %= mod;}return c;}matrix operator + (const matrix& b) const{matrix <t> c(max1(row, b.row), max1(col, b.col));for(int i = 0; i < c.row; i++) for(int j = 0; j < c.col; j++){t a = 0; if(i < row && j < col) a = mat[i][j];t b1 = 0; if(i < b.row && j < b.col) b1 = b.mat[i][j];c.mat[i][j] = a + b1;c.mat[i][j] %= mod;}return c;}matrix operator - (const matrix& b) const{matrix <t> c(max1(row, b.row), max1(col, b.col));for(int i = 0; i < c.row; i++) for(int j = 0; j < c.col; j++){t a = 0; if(i < row && j < col) a = mat[i][j];t b1 = 0; if(i < b.row && j < b.col) b1 = b.mat[i][j];c.mat[i][j] = a - b1;}return c;}inline void operator = (const matrix & b){memcpy(mat, b.mat, sizeof(mat));col = b.col;  row = b.row;}matrix pow(int n){matrix <t> ans(row, col), temp = *this;ans.danweiju();while(n){if(n & 1) ans = ans * temp;temp = temp * temp;n >>= 1;}return ans;}int inv(){int i, j, k, is[maxn], js[maxn];double t1;if (row != col) return 0;for(k = 0; k < row; k++){for(t1 = 0,i = k; i < row; i++) for(j = k; j < row; j++)if(fabs(mat[i][j]) > t1)t1=fabs(mat[is[k] = i][js[k] = j]);if (fabs(t1 - 0) < 1e-9) return 0;if (is[k] != k) for(j = 0; j < row; j++)t1 = mat[k][j], mat[k][j] = mat[is[k]][j], mat[is[k]][j] = t1;if (js[k] != k) for (i = 0; i < row; i++)t1 = mat[i][k], mat[i][k] = mat[i][js[k]], mat[i][js[k]] = t1;mat[k][k] = 1 / mat[k][k];for(j = 0; j < row; j++) if (j != k)mat[k][j] *= mat[k][k];for (i = 0; i < row; i++)    if (i != k)for (j = 0; j < row; j++) if (j != k)mat[i][j] -= mat[i][k] * mat[k][j];for (i = 0;i < row; i++) if (i != k)mat[i][k] *= -mat[k][k];}for (k = row-1; k >= 0; k--){for (j = 0; j < row; j++) if (js[k] != k)t1 = mat[k][j], mat[k][j] = mat[js[k]][j], mat[js[k]][j]=t1;for (i = 0; i < row; i++) if (is[k] != k)t1 = mat[i][k], mat[i][k] = mat[i][is[k]], mat[i][is[k]] = t1;}return 1;}double det(){int i, j, k, sign = 0;double b[maxn][maxn], ret = 1, t1;if (row != col) return 0;for (i = 0; i < row; i++) for (j = 0; j < col; j++)b[i][j] = mat[i][j];for (i = 0; i < row; i++){if (fabs(b[i][i] - 0) < 1e-9){for (j = i + 1; j < row; j++)if (fabs(b[j][i] - 0) > 1e-9) break;if (j == row) return 0;for (k = i; k < row; k++)t1 = b[i][k], b[i][k] = b[j][k], b[j][k] = t1;sign++;}ret *= b[i][i];for (k = i + 1; k < row; k++) b[i][k] /= b[i][i];for (j = i + 1; j < row; j++) for (k = i + 1; k < row; k++)b[j][k] -= b[j][i] * b[i][k];}if (sign & 1) ret = -ret;return ret;}
};const int trans[42][2] = {{1, 3}, {1, 9}, {2, 3}, {2, 18}, {4, 12}, {4, 36}, {8, 12}, {8, 72}, {8, 9}, {8, 24}, {16, 24}, {16, 18}, {32, 36}, {32, 96}, {64, 96}, {64, 72},{3, 1}, {3, 2}, {12, 4}, {12, 8}, {24, 8}, {24, 16}, {96, 32}, {96, 64}, {36, 4}, {36, 32}, {9, 1}, {9, 8}, {72, 8}, {72, 64}, {18, 2}, {18, 16}, {11, 0}, {19, 0}, {13, 0}, {44, 0}, {76, 0}, {25, 0}, {26, 0}, {88, 0}, {100, 0}, {104, 0}};
vi wh[100];
ll dp[128][128];
bool f[128][128];
pii q[1 << 15];
int lq, rq;
int ncase, n;
char str[10];
matrix <ll> m(128, 128);int main(){for(int i = 0; i < 42; i++){int k = lb(trans[i][0]);wh[k].push_back(i);}for(int i = 0; i < 128; i++){memset(dp, 0, sizeof(dp));memset(f, 0, sizeof(f));dp[i][0] = 1; rq = 1; f[i][0] = 1;q[lq = 0] = make_pair(i, 0);for(; rq != lq; ){int wh1 = lb(q[lq].first + 1);for(int j = 0; j < (int)wh[wh1].size(); j++){if((q[lq].first & trans[wh[wh1][j]][0]) || (q[lq].second & trans[wh[wh1][j]][1])) continue;pii p;p.first = q[lq].first | trans[wh[wh1][j]][0];p.second = q[lq].second | trans[wh[wh1][j]][1];dp[p.first][p.second] += dp[q[lq].first][q[lq].second];if(p.first != 127 && f[p.first][p.second] == 0){f[p.first][p.second] = 1;q[rq++] = p;}}lq++;}for(int j = 0; j < 128; j++) m.mat[i][j] = dp[127][j];}while(scanf("%d", &n) != -1){for(int i = 0; i < 7; i++)while(str[i] != 48 && str[i] != 49)scanf("%c", str + i);int num = 0;for(int i = 0; i < 7; i++) num += (str[i] - 48) << i;m = m.pow(n - 1);ll ans = m.mat[0][num];for(int i = 0; i < 127; i++){for(int j = 32; j < 42; j++)if(((i & trans[j][0]) == 0) && ((i | trans[j][0]) == num)){ans += m.mat[0][i];break;}}if(num == 127) ans += m.mat[0][2] + m.mat[0][8] + m.mat[0][32];cout << num << ' ' << ans % mod << endl;}return 0;
}