Description：

一个字符串每一位为 $1,2,3$ ，让某一位在模3意义下加一的代价分别为 $v_1,v_2,v_3$ ，求在总代价不超过 $n$ 的情况下从串 $S$ 变成串 $T$ 。

$1\leqslant|S|\leqslant 13$

Solution：

因为各位之间独立，首先可以计算出把 $S$ 用最少步变成 $T$ 的花费，然后剩下的就是在一些位上累加 $1,2,3$ 的循环，于是可以计算出最多能累加的循环个数，把 $S[i]$ 变成 $T[i]-S[i]$ ，然后就是把 $S$ 变成全为 $1$ 的串，我们可以把一个串看成一个状态，给某一位加一可以看成状态之间的转移边，于是问题就变成了路径计数问题，于是可以想到用矩阵快速幂，但是点数有 $3^l$ ，发现对于最终结果来说，每一位都是一样的，因此可以交换一些位，然后我们可以发现，所有 $1,2,3$ 个数相同的状态本质相同，因此可以把它们合并在一起，于是状态数就变成了 $\binom {15} 2=105$ ，就可以用矩阵加速了，但是由于还要求 $n$ 为每个值时的前缀和，因此就像数列求前缀和那样在另记一位前缀和就行了。

重要性质是某一位的每次操作是固定的，因此我们只需要知道他最终进行了几步就可以一定保证合法。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cctype>

#include<cstring>

using namespace std;

int v1,v2,v3,n;

#define MAXN 20

char c1[MAXN],c2[MAXN];

int v[MAXN];

#define MOD 1000000007

int power(int a,int b)

{

	int res = 1;

	while(b > 0)

	{

		if(b & 1)res = 1ll * res * a % MOD;

		a = 1ll * a * a % MOD;

		b = b >> 1;

	}

	return res;

}

int d[MAXN];

map<pair<int,int>,int> id_;

int tot = 0;

int id(int x,int y)

{

	if(id_[make_pair(x,y)] == 0)id_[make_pair(x,y)] = ++tot;

	return id_[make_pair(x,y)];

}

#define MOD 1000000007

struct matrix

{

	int m[120][120];

	matrix(){memset(m,0,sizeof(m));}

	friend matrix operator * (matrix a,matrix b)

	{

		matrix c;

		for(int i = 0;i <= tot;++i)

			for(int j = 0;j <= tot;++j)

				for(int k = 0;k <= tot;++k)

					c.m[i][j] = (c.m[i][j] + 1ll * a.m[i][k] * b.m[k][j] % MOD) % MOD;

		return c;

	}

	friend matrix operator ^ (matrix a,int b)

	{

		matrix res = a;--b;

		while(b > 0)

		{

			if(b & 1)res = res * a;

			a = a * a;

			b = b >> 1;

		}

		return res;

	}

};

int main()

{

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

	scanf("%d%d%d%d",&v1,&v2,&v3,&n);

	scanf("%s%s",c1 + 1,c2 + 1);

	int l = strlen(c1 + 1);

	int cnt[3] = {0,0,0};

	for(int i = 1;i <= l;++i)

	{

		if(c1[i] == 'C')c1[i] = 0;

		if(c1[i] == 'A')c1[i] = 1;

		if(c1[i] == 'T')c1[i] = 2;

		if(c2[i] == 'C')c2[i] = 0;

		if(c2[i] == 'A')c2[i] = 1;

		if(c2[i] == 'T')c2[i] = 2;

		d[i] = (c2[i] - c1[i] + 3) % 3;

		++cnt[d[i]];

		while(c1[i] != c2[i])

		{

			if(c1[i] == 0)n -= v1;

			if(c1[i] == 1)n -= v2;

			if(c1[i] == 2)n -= v3;

			c1[i] = (c1[i] + 1) % 3;

			++v[i];

			if(n < 0){puts("0");return 0;}

		}

	}

	if(n < 0){puts("0");return 0;}

	int t = n / (v1 + v2 + v3) * 3;

	for(int i = 1;i <= l;++i)t += v[i];

	matrix f;

	for(int i = 0;i <= l;++i)

	{

		for(int j = 0;j <= l - i;++j)

		{

			if(i > 0)f.m[id(i,j)][id(i - 1,j + 1)] = i;

			if(j > 0)f.m[id(i,j)][id(i,j - 1)] = j;

			if(l - i - j > 0)f.m[id(i,j)][id(i + 1,j)] = l - i - j;

		}

	}

	f.m[0][0] = 1;f.m[id(l,0)][0] = 1;

	matrix res = f ^ (t + 1);

	cout << res.m[id(cnt[0],cnt[2])][0] << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}