题解 蛇

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 2010
#define ll long long 
#define ull unsigned long long
//#define int long long 

int n, m;
char mp[3][N], s[N];
const ll p=1e9+7, base=131;
const int dlt[][2]={{-1,0},{1,0},{0,1},{0,-1}};

namespace force{
	bool vis[3][N];
	ll ans;
	void dfs(int x, int y, int back, int pos) {
		//cout<<"dfs "<<x<<' '<<y<<' '<<back<<' '<<pos<<endl;
		if (pos==m) {++ans; return ;}
		vis[x][y]=1;
		for (int i=0,x2,y2; i<4; ++i) if (i!=back) {
			x2=x+dlt[i][0], y2=y+dlt[i][1];
			if (x2>=1&&x2<=2&&y2>=1&&y2<=n&&mp[x2][y2]==s[pos+1]&&!vis[x2][y2])
				dfs(x2, y2, i^1, pos+1);
		}
		vis[x][y]=0;
	}
	void solve() {
		for (int i=1; i<=2; ++i) 
			for (int j=1; j<=n; ++j)
				if (mp[i][j]==s[1]) dfs(i, j, 4, 1); //, cout<<"return "<<endl;
		printf("%lld\n", ans%p);
		exit(0);
	}
}

namespace task{
	ll dp[2][N][N][2]; short hd[2][N][N], tail[2][N][N];
	ull sh[N], h[3][N], b[N];
	inline ull hashing(ull* h, int l, int r) {return h[r]-h[l-1]*b[r-l+1];}
	ll solve(bool op) {
		//cout<<double(sizeof(dp)+sizeof(hd))/1024/1024<<endl;
		memset(dp, 0, sizeof(dp));
		memset(hd, 0, sizeof(hd));
		memset(tail, 0, sizeof(tail));
		b[0]=1; ll ans=0;
		for (int i=1; i<=n; ++i) b[i]=b[i-1]*base;
		for (int i=1; i<=m; ++i) sh[i]=sh[i-1]*base+s[i];
		for (int i=1; i<=n; ++i) h[1][i]=h[1][i-1]*base+mp[1][i];
		for (int i=1; i<=n; ++i) h[2][i]=h[2][i-1]*base+mp[2][i];
		for (int i=1; i<=n; ++i) if (mp[1][i]==s[1]) {
			++dp[0][i][1][0];
			for (int j=i-1; j&&mp[1][j]==s[i-j+1]; --j)
				if (hashing(h[2], j, i)==hashing(sh, i-j+2, 2*i-2*j+2)) {
					if (2*i-2*j+2==m && (m!=2||op)) ++ans;
					else if (i<n && mp[2][i+1]==s[2*i-2*j+3]) {
						++dp[1][i+1][2*i-2*j+3][0]; //, cout<<"1: "<<i<<' '<<j<<endl;
						++tail[1][i][2*i-2*j+2];
					}
				}
		}
		for (int i=1; i<=n; ++i) if (mp[2][i]==s[1]) {
			++dp[1][i][1][0];
			for (int j=i-1; j&&mp[2][j]==s[i-j+1]; --j)
				if (hashing(h[1], j, i)==hashing(sh, i-j+2, 2*i-2*j+2)) {
					if (2*i-2*j+2==m && (m!=2||op)) ++ans;
					else if (i<n && mp[1][i+1]==s[2*i-2*j+3]) {
						++dp[0][i+1][2*i-2*j+3][0]; //, cout<<"2: "<<i<<' '<<j<<endl;
						++tail[0][i][2*i-2*j+2];
					}
				}
		}
		for (int i=1; i<=n; ++i) if (mp[1][i]==s[m]) {
			//cout<<"i: "<<i<<' '<<mp[1][i]<<' '<<s[m]<<endl;
			for (int j=i+1; j<=n&&mp[1][j]==s[m-j+i]; ++j) {
				//cout<<"j: "<<mp[1][j]<<' '<<s[m-j+i]<<endl;
				//cout<<i<<' '<<j<<' '<<m-2*j+2*i-1<<' '<<m-j+i-1<<endl;
				//cout<<hashing(h[2], i, j)<<' '<<hashing(sh, m-2*j+2*i-1, m-j+i-1)<<endl;
				if (hashing(h[2], i, j)==hashing(sh, m-2*j+2*i-1, m-j+i-1)) {
					//cout<<"check: "<<mp[2][i-1]<<' '<<s[m-2*j+2*i-2]<<' '<<m-2*j+2*i-1<<endl;
					if (2*j-2*i+2==m && (m!=2||op)) ; //cout<<"error1"<<endl;
					else if (i>1 && mp[2][i-1]==s[m-2*j+2*i-2])
						++hd[1][i-1][m-2*j+2*i-2]; //, cout<<3<<' '<<i<<' '<<j<<endl;
				}
			}
		}
		for (int i=1; i<=n; ++i) if (mp[2][i]==s[m]) {
			//cout<<"i: "<<mp[2][i]<<' '<<s[m]<<endl;
			for (int j=i+1; j<=n&&mp[2][j]==s[m-j+i]; ++j) {
				//cout<<"j: "<<mp[2][j]<<' '<<s[m-j+i]<<endl;
				//cout<<hashing(h[1], i, j)<<' '<<hashing(sh, m-2*j+2*i-1, m-j+i-1)<<endl;
				//cout<<i<<' '<<j<<' '<<m-2*j+2*i-1<<' '<<m-j+i-1<<endl;
				if (hashing(h[1], i, j)==hashing(sh, m-2*j+2*i-1, m-j+i-1)) {
					//cout<<"hash accepted "<<' '<<i<<' '<<mp[1][i-1]<<' '<<s[m-2*j+2*i-2]<<endl;
					if (2*j-2*i+2==m && (m!=2||op)) ; //cout<<"error2"<<endl;
					else if (i>1 && mp[1][i-1]==s[m-2*j+2*i-2])
						++hd[0][i-1][m-2*j+2*i-2]; //, cout<<4<<' '<<i<<' '<<j<<endl;
				}
			}
		}
		//cout<<"ans: "<<ans<<endl;
		#if 0
		cout<<"ans: "<<ans<<endl;
		for (int i=1; i<=n; ++i) cout<<dp[0][i]<<' '; cout<<endl;
		for (int i=1; i<=n; ++i) cout<<dp[1][i]<<' '; cout<<endl;
		for (int i=1; i<=n; ++i) {
			cout<<dp[0][i]<<' ';
			for (int j=1; j<=m; ++j) cout<<dp[0][i][j][0]<<' '; cout<<endl;
		}
		for (int i=1; i<=n; ++i) {
			cout<<dp[1][i]<<' ';
			for (int j=1; j<=m; ++j) cout<<dp[1][i][j][0]<<' '; cout<<endl;
		}
		#endif
		for (int j=1; j<=n; ++j)
			for (int k=1; k<=m; ++k) {
				dp[0][j][k][1]=dp[0][j][k][0];
				dp[1][j][k][1]=dp[1][j][k][0];
			}
		for (int j=1; j<=n; ++j) {
			for (int k=1; k<=m; ++k) {
				#if 0
				printf("dp[%d][%d][%d][%d]=%lld\n", 1, j, k, 0, dp[0][j][k][0]);
				printf("dp[%d][%d][%d][%d]=%lld\n", 1, j, k, 1, dp[0][j][k][1]);
				printf("dp[%d][%d][%d][%d]=%lld\n", 2, j, k, 0, dp[1][j][k][0]);
				printf("dp[%d][%d][%d][%d]=%lld\n", 2, j, k, 1, dp[1][j][k][1]);
				//cout<<"now ans="<<ans<<endl;
				#endif
				if (mp[1][j]==s[k]) {
					if ((m>2||op) && mp[2][j]==s[k+1]) dp[1][j][k+1][1]=(dp[1][j][k+1][1]+dp[0][j][k][0])%p;
					if (mp[1][j+1]==s[k+1]) {
						dp[0][j+1][k+1][1]=(dp[0][j+1][k+1][1]+dp[0][j][k][1])%p;
						dp[0][j+1][k+1][0]=(dp[0][j+1][k+1][0]+dp[0][j][k][1])%p;
					}
				}
				if (mp[2][j]==s[k]) {
					if ((m>2||op) && mp[1][j]==s[k+1]) dp[0][j][k+1][1]=(dp[0][j][k+1][1]+dp[1][j][k][0])%p;
					if (mp[2][j+1]==s[k+1]) {
						dp[1][j+1][k+1][1]=(dp[1][j+1][k+1][1]+dp[1][j][k][1])%p;
						dp[1][j+1][k+1][0]=(dp[1][j+1][k+1][0]+dp[1][j][k][1])%p;
					}
				}
				ans=(ans+dp[0][j][k][1]*hd[0][j][k]+dp[1][j][k][1]*hd[1][j][k])%p;
				//printf("able hd: %lld %lld\n", hd[0][j][k], hd[1][j][k]);
				//printf("add hd: %lld %lld\n", dp[0][j][k][1]*hd[0][j][k], dp[1][j][k][1]*hd[1][j][k]);
				ans=(ans+tail[0][j][k]*hd[0][j][k]+tail[1][j][k]*hd[1][j][k])%p;
			}
			ans=(ans+dp[0][j][m][1]+dp[1][j][m][1])%p;
			//printf("add: %lld %lld\n", dp[0][j][m][1], dp[1][j][m][1]);
		}
		return ans;
	}
}

signed main()
{
	scanf("%s%s%s", mp[1]+1, mp[2]+1, s+1);
	n=strlen(mp[1]+1); m=strlen(s+1);
	//force::solve();
	ll ans=task::solve(1);
	//cout<<"first iterator: "<<ans<<endl;
	reverse(mp[1]+1, mp[1]+n+1);
	reverse(mp[2]+1, mp[2]+n+1);
	printf("%lld\n", (ans+(m!=1?task::solve(0):0))%p);
	
	return 0;
}