using Lib;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Diagnostics.Contracts;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Runtime.Intrinsics;
using System.Text;
using static Lib.OutputLib;
public class Solver
{
    const bool MultiTestCase = false;
    void Solve()
    {
        var t = rs;
        long k = rl;

        ModMatrix<M>.SetMod(1000000007);
        var a = new ModMatrix<M>(6, 6);
        for (int i = 0; i < 6; i++) a[i, i] = 1;
        var b = new ModMatrix<M>[2];
        for (int v = 0; v < 2; v++)
        {
            b[v] = new ModMatrix<M>(6, 6);
            int x = v * 3, y = (v ^ 1) * 3;
            for (int i = 0; i < 6; i++) b[v][i, i] = 1;
            b[v][x, y] = 1;
            b[v][x + 1, y] = 1;
            b[v][x + 1, y + 1] = 1;
            b[v][x + 2, y] = 1;
            b[v][x + 2, y + 1] = 2;
            b[v][x + 2, y + 2] = 1;
        }
        foreach (var c in t) a = b[c - '0'] * a;
        a = a.Pow(k);
        StaticModInt<Mod1000000007> ans = 0;
        ans += a[2, 0] + a[2, 3];
        ans += a[5, 0] + a[5, 3];
        Write(ans);
    }

    struct M : IMatrixModID { }


#pragma warning disable CS0162, CS8618
    public Solver() { if (!MultiTestCase) Solve(); else for (int t = ri; t > 0; t--) Solve(); }
#pragma warning restore CS0162, CS8618

    const int IINF = 1 << 30;
    const long INF = 1L << 60;
    int ri { [MethodImpl(256)] get => (int)sc.Integer(); }
    long rl { [MethodImpl(256)] get => sc.Integer(); }
    uint rui { [MethodImpl(256)] get => (uint)sc.UInteger(); }
    ulong rul { [MethodImpl(256)] get => sc.UInteger(); }
    double rd { [MethodImpl(256)] get => sc.Double(); }
    string rs { [MethodImpl(256)] get => sc.Scan(); }
    string rline { [MethodImpl(256)] get => sc.Line(); }
    public StreamScanner sc = new StreamScanner(Console.OpenStandardInput());
    void ReadArray(out int[] a, int n) { a = new int[n]; for (int i = 0; i < a.Length; i++) a[i] = ri; }
    void ReadArray(out long[] a, int n) { a = new long[n]; for (int i = 0; i < a.Length; i++) a[i] = rl; }
    void ReadArray<T>(out T[] a, int n, Func<T> read) { a = new T[n]; for (int i = 0; i < a.Length; i++) a[i] = read(); }
    void ReadArray<T>(out T[] a, int n, Func<int, T> read) { a = new T[n]; for (int i = 0; i < a.Length; i++) a[i] = read(i); }
}

static class Program
{
    static public void Main(string[] args)
    {
        SourceExpander.Expander.Expand();
        Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
        new Solver();
        Console.Out.Flush();
    }

}
#region Expanded by https://github.com/kzrnm/SourceExpander
namespace Lib{public partial class StreamScanner{public StreamScanner(Stream stream){str=stream;}private readonly Stream str;private readonly byte[]buf=new byte[1024];private int len,ptr;public bool isEof=false;public bool IsEndOfStream{get{return isEof;}}[MethodImpl(256)]private byte Read(){if(isEof)throw new EndOfStreamException();if(ptr>=len){ptr=0;if((len=str.Read(buf,0,1024))<=0){isEof=true;return 0;}}return buf[ptr++];}[MethodImpl(256)]public char Char(){byte b;do b=Read();while(b<33||126<b);return(char)b;}[MethodImpl(256)]public string Line(){var sb=new StringBuilder();for(var b=Char();b!=10&&!isEof;b=(char)Read())sb.Append(b);return sb.ToString();}[MethodImpl(256)]public string Scan(){var sb=new StringBuilder();for(var b=Char();b>=33&&b<=126;b=(char)Read())sb.Append(b);return sb.ToString();}[MethodImpl(256)]public long Integer(){long ret=0;var ng=false;byte b;do b=Read();while(b!='-'&&(b<'0'||'9'<b));if(b=='-'){ng=true;b=Read();}for(;'0'<=b&&b<='9';b=Read())ret=ret*10+(b^'0');return ng?-ret:ret;}[MethodImpl(256)]public ulong UInteger(){ulong ret=0;byte b;do b=Read();while(b<'0'||'9'<b);for(;'0'<=b&&b<='9';b=Read())ret=ret*10+(ulong)(b^'0');return ret;}[MethodImpl(256)]public double Double()=>double.Parse(Scan());}}
namespace Lib{public class Barrett{public readonly uint Mod;public readonly ulong IM;public Barrett(uint m){Mod=m;IM=unchecked((ulong)-1)/m+1;}[MethodImpl(256)]public uint Mul(uint a,uint b)=>Reduce((ulong)a*b);[MethodImpl(256)]public uint Reduce(ulong z){var x=InternalMath.Mul128Bit(z,IM);var v=unchecked((uint)(z-x*Mod));if(Mod<=v)v+=Mod;return v;}[MethodImpl(256)]public uint Pow(long x,long n){if(Mod==1)return 0;uint r=1,y=(uint)InternalMath.SafeMod(x,Mod);while(n>0){if((n&1)!=0)r=Mul(r,y);y=Mul(y,y);n>>=1;}return r;}}}
namespace Lib{public static class InternalMath{private static readonly Dictionary<uint,int>primitiveRootsCache=new Dictionary<uint,int>(){{2,1},{167772161,3},{469762049,3},{754974721,11},{998244353,3}};[MethodImpl(256)]public static int PrimitiveRoot<TMod>()where TMod:struct,IStaticMod{uint m=default(TMod).Mod;if(primitiveRootsCache.TryGetValue(m,out var p))return p;return primitiveRootsCache[m]=PrimitiveRootCalculate<TMod>();}static int PrimitiveRootCalculate<TMod>()where TMod:struct,IStaticMod{var m=default(TMod).Mod;Span<uint>divs=stackalloc uint[20];divs[0]=2;int cnt=1;var x=m-1;x>>=BitOperations.TrailingZeroCount(x);for(uint i=3;(long)i*i<=x;i+=2){if(x%i==0){divs[cnt++]=i;do{x/=i;}while(x%i==0);}}if(x>1){divs[cnt++]=x;}divs=divs.Slice(0,cnt);for(int g=2;;g++){foreach(var d in divs)if(new StaticModInt<TMod>(g).Pow((m-1)/d).Value==1)goto NEXT;return g;NEXT:;}}[MethodImpl(256)]public static int PrimitiveRoot(uint m){if(primitiveRootsCache.TryGetValue(m,out var p))return p;return primitiveRootsCache[m]=PrimitiveRootCalculate(m);}static int PrimitiveRootCalculate(uint m){Span<uint>divs=stackalloc uint[20];divs[0]=2;int cnt=1;var x=m-1;x>>=BitOperations.TrailingZeroCount(x);for(uint i=3;(long)i*i<=x;i+=2){if(x%i==0){divs[cnt++]=i;do{x/=i;}while(x%i==0);}}if(x>1){divs[cnt++]=x;}divs=divs.Slice(0,cnt);ulong Pow(ulong x,uint n){ulong y=1;while(n>0){if((n&1)==1)y=y*x%m;x=x*x%m;n/=2;}return y;}for(uint g=2;;g++){foreach(var d in divs)if(Pow(g,(m-1)/d)==1)goto NEXT;return(int)g;NEXT:;}}[MethodImpl(256)]public static(long,long)InvGcd(long a,long b){a=SafeMod(a,b);if(a==0)return(b,0);long s=b,t=a;long m0=0,m1=1;long u;while(true){if(t==0){if(m0<0)m0+=b/s;return(s,m0);}u=s/t;s-=t*u;m0-=m1*u;if(s==0){if(m1<0)m1+=b/t;return(t,m1);}u=t/s;t-=s*u;m1-=m0*u;}}[MethodImpl(256)]public static long SafeMod(long x,long m){x%=m;if(x<0)x+=m;return x;}[MethodImpl(256)]public static bool IsPrime(int n){if(n<=1)return false;if(n==2||n==7||n==61)return true;if(n%2==0)return false;long d=n-1;while(d%2==0)d/=2;ReadOnlySpan<byte>bases=stackalloc byte[3]{2,7,61};foreach(long a in bases){long t=d;long y=PowMod(a,t,n);while(t!=n-1&&y!=1&&y!=n-1){y=y*y%n;t<<=1;}if(y!=n-1&&t%2==0){return false;}}return true;}[MethodImpl(256)]public static uint PowMod(long x,long n,int m){if(m==1)return 0;return new Barrett((uint)m).Pow(x,n);}[MethodImpl(256)]public static uint PowMod(long x,long n,uint m){if(m==1)return 0;return new Barrett(m).Pow(x,n);}[MethodImpl(256)]public static ulong FloorSumUnsigned(ulong n,ulong m,ulong a,ulong b){ulong ans=0;while(true){if(a>=m){ans+=(n-1)*n/2*(a/m);a%=m;}if(b>=m){ans+=n*(b/m);b%=m;}ulong yMax=a*n+b;if(yMax<m)return ans;(n,m,a,b)=(yMax/m,a,m,yMax%m);}}[MethodImpl(256)]public static ulong Mul128Bit(ulong a,ulong b){if(System.Runtime.Intrinsics.X86.Bmi2.X64.IsSupported)return System.Runtime.Intrinsics.X86.Bmi2.X64.MultiplyNoFlags(a,b);return Mul128BitLogic(a,b);}[MethodImpl(256)]internal static ulong Mul128BitLogic(ulong a,ulong b){var au=a>>32;var ad=a&0xFFFFFFFF;var bu=b>>32;var bd=b&0xFFFFFFFF;var l=ad*bd;var m1=au*bd;var m2=ad*bu;var h=au*bu;var lu=l>>32;var m1d=m1&0xFFFFFFFF;var m2d=m2&0xFFFFFFFF;var c=m1d+m2d+lu;return h+(m1>>32)+(m2>>32)+(c>>32);}}}
namespace Lib{public interface IMatrixModID{}public struct MatrixMod1:IMatrixModID{}public struct ModMatrix<ModID>where ModID:struct,IMatrixModID{readonly static int vecLength=Vector256<uint>.Count;static Vector256<uint>vecMod;public static uint Mod{get;private set;}static Barrett bar;static uint Inv(uint x){long u=Mod,xu=1,yu=0,v=x,xv=0,yv=1;while(v!=0){long w=u%v;if(w<0)w+=v;long q=(u-w)/v;long xw=xu-xv*q;long yw=yu-yv*q;u=v;xu=xv;yu=yv;v=w;xv=xw;yv=yw;}return(uint)(yu<0?yu+Mod:yu);}public static void SetMod(uint mod){Mod=mod;bar=new Barrett(Mod);vecMod=Vector256.Create(Mod);}public int Height{get;private set;}public int Width{get;private set;}readonly int size;readonly uint[]mat;[MethodImpl(256)]readonly int GetIndex(int i,int j)=>i*Width+j;[MethodImpl(256)]public readonly uint Get(int i,int j)=>mat[GetIndex(i,j)];[MethodImpl(256)]public readonly uint Set(int i,int j,uint v)=>mat[GetIndex(i,j)]=v;public uint this[int i,int j]{[MethodImpl(256)]get=>mat[GetIndex(i,j)];[MethodImpl(256)]set=>mat[GetIndex(i,j)]=value;}public ModMatrix(int n,int m){Height=n;Width=m;size=n*m;mat=new uint[size];}public ModMatrix(uint[,]_mat){Height=_mat.GetLength(0);Width=_mat.GetLength(1);size=Height*Width;mat=new uint[size];for(int i=0;i<Height;i++)for(int j=0;j<Width;j++)mat[GetIndex(i,j)]=_mat[i,j];}public ModMatrix(ModMatrix<ModID>_mat){Height=_mat.Height;Width=_mat.Width;size=_mat.size;mat=(uint[])_mat.mat.Clone();}public override string ToString(){if(Height==0||Width==0)return "";var sb=new StringBuilder();for(int i=0;i<Height;i++){if(i>0)sb.Append('\n');for(int j=0;j<Width;j++){if(j>0)sb.Append(' ');sb.Append(Get(i,j));}}return sb.ToString();}public static ModMatrix<ModID>operator+(ModMatrix<ModID>a,ModMatrix<ModID>b){Contract.Requires(a.Height==b.Height&&a.Width==b.Width);var c=new ModMatrix<ModID>(a);for(int i=0;i<b.size;i++){c.mat[i]+=b.mat[i];if(c.mat[i]>=Mod)c.mat[i]-=Mod;}return c;}public static ModMatrix<ModID>operator-(ModMatrix<ModID>a,ModMatrix<ModID>b){Contract.Requires(a.Height==b.Height&&a.Width==b.Width);var c=new ModMatrix<ModID>(a);for(int i=0;i<b.size;i++){c.mat[i]-=b.mat[i];if(c.mat[i]>=Mod)c.mat[i]+=Mod;}return c;}public static ModMatrix<ModID>operator*(ModMatrix<ModID>a,ModMatrix<ModID>b){Contract.Requires(a.Width==b.Height);var c=new ModMatrix<ModID>(a.Height,b.Width);Multiply(a.GetSubmatrixInfo(),a.mat,b.GetSubmatrixInfo(),b.mat,c.GetSubmatrixInfo(),c.mat);return c;}[MethodImpl(256)]readonly SubmatrixInfo GetSubmatrixInfo()=>new SubmatrixInfo(Height,Width);struct SubmatrixInfo{public readonly int Height0,Width0,LX,LY,RX,RY;public readonly int Height=>RX-LX;public readonly int Width=>RY-LY;public SubmatrixInfo(int h0,int w0){Height0=h0;Width0=w0;LX=0;LY=0;RX=h0;RY=w0;}SubmatrixInfo(int h0,int w0,int lx,int ly,int rx,int ry){Height0=h0;Width0=w0;LX=lx;LY=ly;RX=rx;RY=ry;}[MethodImpl(256)]public readonly int GetIndex(int x,int y)=>(LX+x)*Width0+LY+y;[MethodImpl(256)]public readonly SubmatrixInfo Slice(int lx,int sx,int ly,int sy){lx+=LX;int rx=lx+sx;ly+=LY;int ry=ly+sy;return new SubmatrixInfo(Height0,Width0,lx,ly,rx,ry);}[MethodImpl(256)]public readonly SubmatrixInfo LastRow()=>Slice(Height-1,1,0,Width);[MethodImpl(256)]public readonly SubmatrixInfo LastCol()=>Slice(0,Height,Width-1,1);}static void Multiply(SubmatrixInfo ma,ReadOnlySpan<uint>a,SubmatrixInfo mb,ReadOnlySpan<uint>b,SubmatrixInfo mc,Span<uint>c){int n1=ma.Height,n2=ma.Width,n3=mb.Width;const int NAIVE_SIZE=64;if(n1<=NAIVE_SIZE||n2<=NAIVE_SIZE||n3<=NAIVE_SIZE){MultiplyNaive(ma,a,mb,b,mc,c);}else{MultiplyStrassen(ma,a,mb,b,mc,c);}}[MethodImpl(256)]static void MultiplyNaive(SubmatrixInfo ma,ReadOnlySpan<uint>a,SubmatrixInfo mb,ReadOnlySpan<uint>b,SubmatrixInfo mc,Span<uint>c){Clear(mc,c);int n1=ma.Height,n2=ma.Width,n3=mb.Width;for(int i=0;i<n1;i++){var arow=a.Slice(ma.GetIndex(i,0),n2);var crow=c.Slice(mc.GetIndex(i,0),n3);for(int k=0;k<arow.Length;k++){uint val=arow[k];var brow=b.Slice(mb.GetIndex(k,0),crow.Length);for(int j=0;j<crow.Length;j++){crow[j]+=bar.Mul(val,brow[j]);if(crow[j]>=Mod)crow[j]-=Mod;}}}}static void MultiplyStrassen(SubmatrixInfo ma,ReadOnlySpan<uint>a,SubmatrixInfo mb,ReadOnlySpan<uint>b,SubmatrixInfo mc,Span<uint>c){int n1=ma.Height,n2=ma.Width,n3=mb.Width;int m1=n1/2,m2=n2/2,m3=n3/2;if((n2&1)==1){MultiplyNaive(ma.LastCol(),a,mb.LastRow(),b,mc,c);}else{Clear(mc,c);}if((n1&1)==1){MultiplyNaive(ma.LastRow(),a,mb,b,mc.LastRow(),c);}if((n3&1)==1){MultiplyNaive(ma,a,mb.LastCol(),b,mc.LastCol(),c);}var a11=ma.Slice(0,m1,0,m2);var a12=ma.Slice(0,m1,m2,m2);var a21=ma.Slice(m1,m1,0,m2);var a22=ma.Slice(m1,m1,m2,m2);var b11=mb.Slice(0,m2,0,m3);var b12=mb.Slice(0,m2,m3,m3);var b21=mb.Slice(m2,m2,0,m3);var b22=mb.Slice(m2,m2,m3,m3);var c11=mc.Slice(0,m1,0,m3);var c12=mc.Slice(0,m1,m3,m3);var c21=mc.Slice(m1,m1,0,m3);var c22=mc.Slice(m1,m1,m3,m3);Span<uint>ta=stackalloc uint[m1*m2];Span<uint>tb=stackalloc uint[m2*m3];Span<uint>tc=stackalloc uint[m1*m3];var mta=new SubmatrixInfo(m1,m2);var mtb=new SubmatrixInfo(m2,m3);var mtc=new SubmatrixInfo(m1,m3);Add(a11,a,a22,a,ta);Add(b11,b,b22,b,tb);Multiply(mta,ta,mtb,tb,mtc,tc);AddLToR(mtc,tc,c11,c);AddLToR(mtc,tc,c22,c);Add(a21,a,a22,a,ta);Multiply(mta,ta,b11,b,mtc,tc);AddLToR(mtc,tc,c21,c);SubLFromR(mtc,tc,c22,c);Sub(b12,b,b22,b,tb);Multiply(a11,a,mtb,tb,mtc,tc);AddLToR(mtc,tc,c12,c);AddLToR(mtc,tc,c22,c);Sub(b21,b,b11,b,tb);Multiply(a22,a,mtb,tb,mtc,tc);AddLToR(mtc,tc,c11,c);AddLToR(mtc,tc,c21,c);Add(a11,a,a12,a,ta);Multiply(mta,ta,b22,b,mtc,tc);SubLFromR(mtc,tc,c11,c);AddLToR(mtc,tc,c12,c);Sub(a21,a,a11,a,ta);Add(b11,b,b12,b,tb);Multiply(mta,ta,mtb,tb,mtc,tc);AddLToR(mtc,tc,c22,c);Sub(a12,a,a22,a,ta);Add(b21,b,b22,b,tb);Multiply(mta,ta,mtb,tb,mtc,tc);AddLToR(mtc,tc,c11,c);}[MethodImpl(256)]static void Clear(SubmatrixInfo ma,Span<uint>a){int h=ma.Height,w=ma.Width;for(int i=0;i<h;i++)a.Slice(ma.GetIndex(i,0),w).Clear();}[MethodImpl(256)]static void Add(SubmatrixInfo ma,ReadOnlySpan<uint>a,SubmatrixInfo mb,ReadOnlySpan<uint>b,Span<uint>c){int h=ma.Height,w=ma.Width;for(int i=0;i<h;i++){var p=a.Slice(ma.GetIndex(i,0),w);var q=b.Slice(mb.GetIndex(i,0),w);var r=c.Slice(i*w,w);for(int j=0;j<w;j+=vecLength){if(j+vecLength>w){for(;j<w;j++){uint v=p[j]+q[j];if(v>=Mod)v-=Mod;r[j]=v;}}else{var vp=Vector256.Create(p.Slice(j,vecLength));var vq=Vector256.Create(q.Slice(j,vecLength));var v=vp+vq;var geq=Vector256.GreaterThanOrEqual(v,vecMod);v=Vector256.ConditionalSelect(geq,v-vecMod,v);v.CopyTo(r.Slice(j,vecLength));}}}}[MethodImpl(256)]static void Sub(SubmatrixInfo ma,ReadOnlySpan<uint>a,SubmatrixInfo mb,ReadOnlySpan<uint>b,Span<uint>c){int h=ma.Height,w=ma.Width;for(int i=0;i<h;i++){var p=a.Slice(ma.GetIndex(i,0),w);var q=b.Slice(mb.GetIndex(i,0),w);var r=c.Slice(i*w,w);for(int j=0;j<w;j+=vecLength){if(j+vecLength>w){for(;j<w;j++){uint v=p[j]-q[j];if(v>=Mod)v+=Mod;r[j]=v;}}else{var vp=Vector256.Create(p.Slice(j,vecLength));var vq=Vector256.Create(q.Slice(j,vecLength));var v=vp-vq;var geq=Vector256.GreaterThanOrEqual(v,vecMod);v=Vector256.ConditionalSelect(geq,v+vecMod,v);v.CopyTo(r.Slice(j,vecLength));}}}}[MethodImpl(256)]static void AddLToR(SubmatrixInfo ml,ReadOnlySpan<uint>l,SubmatrixInfo mr,Span<uint>r){int h=ml.Height,w=ml.Width;for(int i=0;i<h;i++){var p=l.Slice(ml.GetIndex(i,0),w);var q=r.Slice(mr.GetIndex(i,0),w);for(int j=0;j<w;j+=vecLength){if(j+vecLength>w){for(;j<w;j++){q[j]+=p[j];if(q[j]>=Mod)q[j]-=Mod;}}else{var vp=Vector256.Create(p.Slice(j,vecLength));var vq=Vector256.Create((ReadOnlySpan<uint>)q.Slice(j,vecLength));vq+=vp;var geq=Vector256.GreaterThanOrEqual(vq,vecMod);vq=Vector256.ConditionalSelect(geq,vq-vecMod,vq);vq.CopyTo(q.Slice(j,vecLength));}}}}[MethodImpl(256)]static void SubLFromR(SubmatrixInfo ml,ReadOnlySpan<uint>l,SubmatrixInfo mr,Span<uint>r){int h=ml.Height,w=ml.Width;for(int i=0;i<h;i++){var p=l.Slice(ml.GetIndex(i,0),w);var q=r.Slice(mr.GetIndex(i,0),w);ref var itr=ref MemoryMarshal.GetReference(q);for(int j=0;j<w;j+=vecLength){if(j+vecLength>w){for(;j<w;j++){q[j]-=p[j];if(q[j]>=Mod)q[j]+=Mod;}}else{var vp=Vector256.Create(p.Slice(j,vecLength));var vq=Vector256.Create((ReadOnlySpan<uint>)q.Slice(j,vecLength));vq-=vp;var geq=Vector256.GreaterThanOrEqual(vq,vecMod);vq=Vector256.ConditionalSelect(geq,vq+vecMod,vq);vq.StoreUnsafe(ref itr);itr=ref Unsafe.AddByteOffset(ref itr,vecLength*4);}}}}public static ModMatrix<ModID>Identity(int n){var c=new ModMatrix<ModID>(n,n);for(int i=0;i<n;i++)c[i,i]=1;return c;}[MethodImpl(256)]public readonly ModMatrix<ModID>Pow(long n){Contract.Requires(Width==Height&&n>=0);var a=new ModMatrix<ModID>(this);var r=Identity(Height);while(n>0){if(n%2==1)r*=a;a*=a;n/=2;}return r;}[MethodImpl(256)]public void SwapRows(int u,int v){uint tmp;for(int i=0;i<Width;i++){tmp=this[u,i];this[u,i]=this[v,i];this[v,i]=tmp;}}[MethodImpl(256)]public void SwapColumns(int u,int v){uint tmp;for(int i=0;i<Height;i++){tmp=this[i,u];this[i,u]=this[i,v];this[i,v]=tmp;}}[MethodImpl(256)]public uint Determinant(){Contract.Requires(Height==Width);int n=Height;if(n==0)return 1;if(n==1)return mat[0];var a=new ModMatrix<ModID>(this);uint det=1,inv,coeff;for(int y=0;y<n-1;y++){if(a[y,y]==0){int z=y+1;for(;z<n;z++)if(a[z,y]!=0)break;if(z==n)return 0;a.SwapRows(y,z);if(det!=0)det=Mod-det;}inv=Inv(a[y,y]);for(int x=y+1;x<n;x++){coeff=bar.Mul(a[x,y],inv);for(int z=y;z<n;z++){a[x,z]-=bar.Mul(coeff,a[y,z]);if(a[x,z]>=Mod)a[x,z]+=Mod;}}det=bar.Mul(det,a[y,y]);}det=bar.Mul(det,a[n-1,n-1]);return det;}[MethodImpl(256)]public(int rank,ModMatrix<ModID>mat)RowReduction(){int n=Height,m=Width;var a=new ModMatrix<ModID>(this);uint inv,coeff;int rank=0;for(int k=0;k<m&&rank<n;k++){if(a[rank,k]==0){int y=rank+1;for(;y<n;y++)if(a[y,k]!=0)break;if(y==n)continue;a.SwapRows(rank,y);}inv=Inv(a[rank,k]);for(int j=k;j<m;j++)a[rank,j]=bar.Mul(a[rank,j],inv);for(int i=0;i<n;i++){if(i==rank)continue;coeff=a[i,k];for(int j=k;j<m;j++){a[i,j]-=bar.Mul(coeff,a[rank,j]);if(a[i,j]>=Mod)a[i,j]+=Mod;}}rank++;}return(rank,a);}[MethodImpl(256)]public(bool exist,ModMatrix<ModID>mat)Inverse(){Contract.Requires(Height==Width);int n=Height;var a=new ModMatrix<ModID>(n,n+n);for(int i=0;i<n;i++)for(int j=0;j<n;j++)a[i,j]=this[i,j];for(int i=0;i<n;i++)a[i,n+i]=1;var red=a.RowReduction();if(red.rank<n)return(false,default);bool ok=true;for(int i=0;ok&&i<n;i++)ok&=red.mat[i,i]==1;if(!ok)return(false,default);a=new ModMatrix<ModID>(n,n);for(int i=0;i<n;i++)for(int j=0;j<n;j++)a[i,j]=red.mat[i,j+n];return(true,a);}[MethodImpl(256)]public uint[]CharacteristicPolynomial(){Contract.Requires(Height==Width);int n=Height;if(n==0)return new uint[]{1};var T=new uint[n];for(int y=1;y<n;y++){int y1=y;while(y1<n&&this[y1,y-1]==0)y1++;if(y1==n)continue;if(y!=y1){SwapRows(y,y1);SwapColumns(y,y1);}T[y]=this[y,y-1];for(int y2=y+1;y2<n;y2++)T[y2]=bar.Mul(T[y],this[y2,y-1]);for(int y2=y+1;y2<n;y2++)for(int x=y-1;x<n;x++){this[y2,x]-=bar.Mul(this[y,x],T[y2]);if(this[y2,x]>=Mod)this[y2,x]+=Mod;}for(int y2=0;y2<n;y2++)for(int x=y+1;x<n;x++){this[y2,y]+=bar.Mul(this[y2,x],T[x]);if(this[y2,y]>=Mod)this[y2,y]-=Mod;}}for(int y=0;y<n;y++){uint tmp=1;for(int x=y+1;x<n;x++){tmp=bar.Mul(tmp,this[x,x-1]);if(tmp!=0)tmp=Mod-tmp;this[y,x]=bar.Mul(this[y,x],tmp);}}int n1=n+1;var dp=new uint[n1*n1];dp[0]=1;for(int y=0;y<n;y++){for(int x=0;x<=y;x++){int z1=n1*(y+1)+x+1;dp[z1]-=dp[n1*y+x];if(dp[z1]>=Mod)dp[z1]+=Mod;}for(int x=0;x<=y;x++){int z1=n1*(y+1)+x;dp[z1]+=bar.Mul(dp[n1*y+x],this[y,y]);if(dp[z1]>=Mod)dp[z1]-=Mod;}for(int y2=0;y2<y;y2++)for(int x=0;x<=y2;x++){int z1=n1*(y+1)+x;dp[z1]+=bar.Mul(dp[n1*y2+x],this[y2,y]);if(dp[z1]>=Mod)dp[z1]-=Mod;}}var ret=new uint[n+1];for(int i=0;i<=n;i++){uint v=dp[n1*n+i];if(v>0&&(n&1)==1)v=Mod-v;ret[i]=v;}return ret;}}}
namespace Lib{public interface IStaticMod{uint Mod{get;}bool IsPrime{get;}}public readonly struct Mod1000000007:IStaticMod{public uint Mod=>1000000007;public bool IsPrime=>true;}public readonly struct Mod998244353:IStaticMod{public uint Mod=>998244353;public bool IsPrime=>true;}}
namespace Lib{public readonly struct StaticModInt<T>:IEquatable<StaticModInt<T>>where T:struct,IStaticMod{internal readonly uint _v;private static readonly T op=default;public int Value=>(int)_v;public static int Mod=>(int)op.Mod;public static StaticModInt<T>Zero=>default;public static StaticModInt<T>One=>new StaticModInt<T>(1u);[MethodImpl(256)]public static StaticModInt<T>Raw(int v){var u=unchecked((uint)v);return new StaticModInt<T>(u);}[MethodImpl(256)]public StaticModInt(long v):this(Round(v)){}[MethodImpl(256)]public StaticModInt(ulong v):this((uint)(v%op.Mod)){}[MethodImpl(256)]private StaticModInt(uint v)=>_v=v;public static bool IsZero(StaticModInt<T>x)=>x.Value==0;public static bool IsOne(StaticModInt<T>x)=>x.Value==1;[MethodImpl(256)]private static uint Round(long v){var x=v%op.Mod;if(x<0)x+=op.Mod;return(uint)x;}[MethodImpl(256)]public static StaticModInt<T>operator ++(StaticModInt<T>v){var x=v._v+1;if(x==op.Mod)x=0;return new StaticModInt<T>(x);}[MethodImpl(256)]public static StaticModInt<T>operator --(StaticModInt<T>v){var x=v._v;if(x==0)x=op.Mod;return new StaticModInt<T>(x-1);}[MethodImpl(256)]public static StaticModInt<T>operator+(StaticModInt<T>lhs,StaticModInt<T>rhs){var v=lhs._v+rhs._v;if(v>=op.Mod)v-=op.Mod;return new StaticModInt<T>(v);}[MethodImpl(256)]public static StaticModInt<T>operator-(StaticModInt<T>lhs,StaticModInt<T>rhs){unchecked{var v=lhs._v-rhs._v;if(v>=op.Mod)v+=op.Mod;return new StaticModInt<T>(v);}}[MethodImpl(256)]public static StaticModInt<T>operator*(StaticModInt<T>lhs,StaticModInt<T>rhs)=>new StaticModInt<T>((uint)((ulong)lhs._v*rhs._v%op.Mod));[MethodImpl(256)]public static StaticModInt<T>operator/(StaticModInt<T>lhs,StaticModInt<T>rhs)=>new StaticModInt<T>((uint)((ulong)lhs._v*Inv(rhs._v)%op.Mod));[MethodImpl(256)]public static StaticModInt<T>operator+(StaticModInt<T>v)=>v;[MethodImpl(256)]public static StaticModInt<T>operator-(StaticModInt<T>v)=>new StaticModInt<T>(v._v==0?0:op.Mod-v._v);[MethodImpl(256)]public static bool operator==(StaticModInt<T>lhs,StaticModInt<T>rhs)=>lhs._v==rhs._v;[MethodImpl(256)]public static bool operator!=(StaticModInt<T>lhs,StaticModInt<T>rhs)=>lhs._v!=rhs._v;[MethodImpl(256)]public static implicit operator StaticModInt<T>(int v)=>new StaticModInt<T>(v);[MethodImpl(256)]public static implicit operator StaticModInt<T>(uint v)=>new StaticModInt<T>((long)v);[MethodImpl(256)]public static implicit operator StaticModInt<T>(long v)=>new StaticModInt<T>(v);[MethodImpl(256)]public static implicit operator StaticModInt<T>(ulong v)=>new StaticModInt<T>(v);[MethodImpl(256)]public static implicit operator long(StaticModInt<T>v)=>v._v;[MethodImpl(256)]public static implicit operator ulong(StaticModInt<T>v)=>v._v;[MethodImpl(256)]public StaticModInt<T>Pow(long n){var x=this;var r=new StaticModInt<T>(1U);if(n<0)(x,n)=(x.Inv(),-n);while(n>0){if((n&1)>0)r*=x;x*=x;n>>=1;}return r;}[MethodImpl(256)]public StaticModInt<T>Inv()=>new StaticModInt<T>(Inv(_v));[MethodImpl(256)]static ulong Inv(ulong x){long u=op.Mod,xu=1,yu=0,v=(long)x,xv=0,yv=1;while(v!=0){long w=SafeMod(u,v);long q=(u-w)/v;long xw=xu-xv*q;long yw=yu-yv*q;u=v;xu=xv;yu=yv;v=w;xv=xw;yv=yw;}return(ulong)(yu<0?yu+op.Mod:yu);}[MethodImpl(256)]static long SafeMod(long x,long m){long r=x%m;if(r<0)r+=m;return r;}[MethodImpl(256)]public override string ToString()=>_v.ToString();[MethodImpl(256)]public string ToString(string format,IFormatProvider formatProvider)=>_v.ToString(format,formatProvider);[MethodImpl(256)]public override bool Equals(object?obj)=>obj is StaticModInt<T>m&&Equals(m);[MethodImpl(256)]public bool Equals(StaticModInt<T>other)=>_v==other._v;[MethodImpl(256)]public override int GetHashCode()=>_v.GetHashCode();}}
namespace Lib{public static class OutputLib{[MethodImpl(256)]public static void WriteJoin<T>(string s,IEnumerable<T>t)=>Console.WriteLine(string.Join(s,t));[MethodImpl(256)]public static void WriteMat<T>(T[,]a,string sep=" "){int sz1=a.GetLength(0),sz2=a.GetLength(1);var b=new T[sz2];for(int i=0;i<sz1;i++){for(int j=0;j<sz2;j++)b[j]=a[i,j];WriteJoin(sep,b);}}[MethodImpl(256)]public static void WriteMat<T>(T[][]a,string sep=" "){foreach(var ar in a)WriteJoin(sep,ar);}[MethodImpl(256)]public static void WriteMat<T>(T[][]a,Func<T,string>map,string sep=" "){foreach(var ar in a)WriteJoin(sep,ar.Select(x=>map(x)));}[MethodImpl(256)]public static void Write(object t)=>Console.WriteLine(t.ToString());[MethodImpl(256)]public static void Write(params object[]arg)=>Console.WriteLine(string.Join(" ",arg.Select(x=>x.ToString())));[MethodImpl(256)]public static void Write(string str)=>Console.WriteLine(str);[MethodImpl(256)]public static void WriteFlush(object t){Console.WriteLine(t.ToString());Console.Out.Flush();}[MethodImpl(256)]public static void WriteError(object t)=>Console.Error.WriteLine(t.ToString());[MethodImpl(256)]public static void Flush()=>Console.Out.Flush();[MethodImpl(256)]public static void YN(bool t)=>Console.WriteLine(t?"YES":"NO");[MethodImpl(256)]public static void Yn(bool t)=>Console.WriteLine(t?"Yes":"No");[MethodImpl(256)]public static void yn(bool t)=>Console.WriteLine(t?"yes":"no");[MethodImpl(256)]public static void DeleteLine()=>Console.Write("\x1b[1A\x1b[2K");[MethodImpl(256)]public static void ProgressBar(long now,long total,int blocks=50){int x=(int)((2*now*blocks+1)/(2*total));Console.Write($"\x1b[G[\x1b[42m{string.Concat(Enumerable.Repeat("_",x))}\x1b[0m{string.Concat(Enumerable.Repeat("_",blocks-x))}] : {now} / {total}");}}}
namespace SourceExpander{public class Expander{[Conditional("EXP")]public static void Expand(string inputFilePath=null,string outputFilePath=null,bool ignoreAnyError=true){}public static string ExpandString(string inputFilePath=null,bool ignoreAnyError=true){return "";}}}
#endregion Expanded by https://github.com/kzrnm/SourceExpander