#include #include using namespace atcoder; using namespace std; #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define fin(a) return pt(a) using ll=long long; using ld=long double; using v1=vector; using v2=vector; using v3=vector; using v4=vector; using pll=pair; using mll=map; ll inf=1LL<<60; ld pi=acos(-1); ld eps=1e-10; templateusing ascending_priority_queue=std::priority_queue,greater>; templateusing descending_priority_queue=std::priority_queue; templatebool chmax(T&a,const T&b){if(abool chmin(T&a,const T&b){if(bT max(vector&vec,const T&id){T r=id;for(auto&v:vec)chmax(r,max(v,id));return r;} templateT min(vector&vec,const T&id){T r=id;for(auto&v:vec)chmin(r,min(v,id));return r;} templatepll mima(const T&a,const T&b){return {min(a,b),max(a,b)};} templateT sum(vector&a){return accumulate(all(a),T(0));} templateT popcnt(T a){return __builtin_popcountll(a);} istream&operator>>(istream&is,modint1000000007&x){unsigned int t;is>>t;x=t;return is;} istream&operator>>(istream&is,modint998244353&x){unsigned int t;is>>t;x=t;return is;} istream&operator>>(istream&is,modint&x){unsigned int t;is>>t;x=t;return is;} ostream&operator<<(ostream&os,const modint1000000007&x){os<istream&operator>>(istream&is,pair&p){is>>p.first>>p.second;return is;} templateostream&operator<<(ostream&os,const pair&p){os<istream&operator>>(istream&is,vector&v){for(T&x:v)is>>x;return is;} templateostream&operator<<(ostream&os,const vector&v){for(int i=0;i<(int)v.size();i++){os<int pt_rest(){cout<<'\n';return 0;} templateint pt(){cout<<'\n';return 0;} templateint pt_rest(const T&first,const A&...rest){cout<<" "<int pt(const T&first,const A&...rest){cout<void resize(vector&vec,const H head){vec.resize(head);} templatevoid resize(vector&vec,const H&head,const T...tail){vec.resize(head);for(auto&v:vec)resize(v,tail...);} templatevoid fill(V&x,const T&val){x=val;} templatevoid fill(vector&vec,const T&val){for(auto&v:vec)fill(v,val);} templatevoid vin(istream&is,const int idx,vector&head){is>>head[idx];} templatevoid vin(istream&is,const int idx,vector&head,T&...tail){vin(is>>head[idx],idx,tail...);} templatevoid vin(istream&is,vector&head,T&...tail){for(int i=0;i<(int)head.size();i++)vin(is,i,head,tail...);} templatevoid vin(vector&head,T&...tail){vin(cin,head,tail...);} templatevoid sin(istream&is,H&head){is>>head;} templatevoid sin(istream&is,H&head,T&...tail){sin(is>>head,tail...);} templatevoid sin(H&head,T&...tail){sin(cin,head,tail...);} v1 divisor(ll n){mll m;for(ll i=1;i*i<=n;i++)if(n%i==0){m[i]++;m[n/i]++;}v1 v;for(auto[x,_]:m)v.emplace_back(x);return v;} mll factor(ll n){mll m;for(ll i=2;i*i<=n;i++)while(n%i==0){m[i]++;n/=i;}if(n>1)m[n]++;return m;} ll lsqrt(ll x){assert(x>=0);if(x<=1)return x;ll r=sqrt(x)-1;while((r+1)<=x/(r+1))r++;return r;}; using S=ll; S op(S a,S b){return a+b;} S e(){return 0;} int main(void){ cin.tie(nullptr); ios::sync_with_stdio(false); ll H,W;sin(H,W); vectors(H);cin>>s; v1 dx={1,0},dy={0,1}; v3 g;resize(g,H,W,2); for(ll i=0;i=(H+W-1)/2)continue; ll T=H+W-2-i-j; for(ll k=0;k<=T;k++){ ll l=T-k; if(k>=H or l>=W)continue; if(s[i][j]!=s[k][l])continue; for(ll p=0;p<2;p++){ for(ll q=0;q<2;q++){ ll ni=i+dx[p],nj=j+dy[p]; ll pk=k-dx[q],pl=l-dy[q]; if(ni>=H or nj>=W)continue; if(pk<0 or pl<0)continue; if(s[ni][nj]!=s[pk][pl])continue; if(pk==i or pl==j)g[i][j][p]=1; if(ni<=pk and nj<=pl){ g[i][j][p]=1; g[pk][pl][q]=1; } } } } } } using mint=modint1000000007; vector>dp;resize(dp,H,W); dp[0][0]=1; for(ll i=0;i=H or nj>=W)continue; if(g[i][j][k]==0)continue; dp[ni][nj]+=dp[i][j]; } } } pt(dp[H-1][W-1]); }