#pragma GCC optimize("Ofast") #include using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) #define ALL(v) v.begin(),v.end() #define debug(a) cerr<<#a<<":"< istream& operator>>(istream&is,vector&v){ for(T&p:v)is>>p; return is; } template ostream& operator<<(ostream&os,const vector&v){ if(&os==&cerr)os<<"["; for(int i=0;i struct Mint{ inline static constexpr T mod = MOD; T v; Mint():v(0){} Mint(signed v):v(v){} Mint(long long t){v=t%MOD;if(v<0)v+=MOD;} Mint pow(long long k){ Mint res(1),tmp(v); while(k){ if(k&1)res*=tmp; tmp*=tmp; k>>=1; } return res; } static Mint add_identity(){return Mint(0);} static Mint mul_identity(){return Mint(1);} Mint inv(){return pow(MOD-2);} Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;} Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;} Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;} Mint& operator/=(Mint a){return (*this)*=a.inv();} Mint operator+(Mint a) const{return Mint(v)+=a;} Mint operator-(Mint a) const{return Mint(v)-=a;} Mint operator*(Mint a) const{return Mint(v)*=a;} Mint operator/(Mint a) const{return Mint(v)/=a;} Mint operator+() const{return *this;} Mint operator-() const{return v?Mint(MOD-v):Mint(v);} bool operator==(const Mint a)const{return v==a.v;} bool operator!=(const Mint a)const{return v!=a.v;} static Mint comb(long long n,int k){ Mint num(1),dom(1); for(int i=0;i>(istream&is,Mint &m){is>>m.v;m.v%=MOD;if(m.v<0)m.v+=MOD;return is;} }; using ll=long long; using mint=Mint; mint Factorial[5000000],Finverse[5000000]; inline void Cinit(){ Factorial[0]=1; for(int i=1;i<5e6;i++)Factorial[i]=Factorial[i-1]*mint(i); Finverse[4999999]=mint(1)/Factorial[4999999]; for(int i=4999998;i>=0;i--)Finverse[i]=mint(i+1)*Finverse[i+1]; } mint nCk(int n,int k){ if(n,mint> a,b; }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int h,w;cin>>h>>w; vector s(h); cin>>s; if(s[0][0]!=s.back().back()){ cout<<0< que; map,mint> a,b; a[{0,0}]=b[{h-1,w-1}]=1; que.push({a,b}); int aa=0,bb=h-1+w-1; while(bb-aa>1){ queue nxt; while(que.size()){ auto [a,b]=que.front();que.pop(); vector,mint>> aa(26),bb(26); for(auto it=a.begin();it!=a.end();it=a.erase(it)){ const auto&[y,x]=it->first; if(y+1second; if(x+1second; } for(auto it=b.begin();it!=b.end();it=b.erase(it)){ const auto&[y,x]=it->first; if(y)bb[s[y-1][x]-'a'][{y-1,x}]+=it->second; if(x)bb[s[y][x-1]-'a'][{y,x-1}]+=it->second; } REP(i,26)if(aa[i].size() and bb[i].size()) nxt.push(A{aa[i],bb[i]}); } aa++;bb--; que=nxt; } mint ans=0; while(que.size()){ auto [a,b]=que.front();que.pop(); for(const auto&[yx,val]:a){ if(aa==bb)ans+=val*b[yx]; else{ const auto&[y,x]=yx; ans+=val*(b[{y+1,x}]+b[{y,x+1}]); } } } cout<