#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; struct A{ map,mint> a,b; A()=default; A(map,mint> a,map,mint> b):a(a),b(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,nxt; map,mint> a,b; a[{0,0}]=b[{h-1,w-1}]=1; que.emplace(a,b); int aa=0,bb=h-1+w-1; vector,mint>> av(26),bv(26); while(bb-aa>1){ while(que.size()){ auto&[a,b]=que.front(); 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)bv[s[y-1][x]-'a'][{y-1,x}]+=it->second; if(x)bv[s[y][x-1]-'a'][{y,x-1}]+=it->second; } REP(i,26){ if(av[i].size() and bv[i].size()) nxt.emplace(av[i],bv[i]); av[i].clear();bv[i].clear(); } que.pop(); } aa++;bb--; swap(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<