#include<bits/stdc++.h>
using namespace std;
int f[2][201][201],s[2][201][201];//设s[ i ][ j ][ k ]为A用到了 i ，B用到了 j ，已经用了 k 个子串， 并且一定用了当前字符(A[i])时的方案数。
//设f[ i ][ j ][ k ]为A用到了 i ，B用到了 j ，已经用了 k 个子串， 无论用不用当前字符(A[i])时的方案数总和。
int n,m,k,now=1,last=0;
const int mod=1000000007;
char sa[1001],sb[201];
int main()
{
	scanf("%d %d %d",&n,&m,&k);
	scanf("%s",sa+1);
	scanf("%s",sb+1);
	f[0][0][0]=1;
	for(int i=1;i<=n;i++)
	{
		f[now][0][0]=1;
		for(int j=1;j<=m;j++)
		for(int v=1;v<=k;v++)
		{
			if(sa[i]==sb[j])
			{
				s[now][j][v]=(s[last][j-1][v]+f[last][j-1][v-1])%mod;
			}
			else
			{
				s[now][j][v]=0;
			}
			f[now][j][v]=(s[now][j][v]+f[last][j][v])%mod;
		}swap(now,last);	
	}
	printf("%d",f[last][m][k]);
	return 0;
}
/*
[i][j-1][k-1]+=f[i-1][j-1][k-1]
f[i][j][k]+=f[i-1][j-1][k]+f[l][j-1][k-1]
*/

#include<cstdio>
#include<algorithm>
using namespace std;
int s[10][10],n;
int dp[10][10][10][10];
int main()
{
	scanf("%d",&n);
	int x,y,z;
	while(scanf("%d%d%d",&x,&y,&z)&&x!=0&&y!=0&&z!=0)
	{
		s[x][y]=z;
	}
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	for(int a=1;a<=n;a++)
	for(int b=1;b<=n;b++)
	{
		dp[i][j][a][b]=max(max(dp[i-1][j][a-1][b],dp[i-1][j][a][b-1]),max(dp[i][j-1][a-1][b],dp[i][j-1][a][b-1]))+s[i][j]+s[a][b];
		if(i==a&&j==b) dp[i][j][a][b]-=s[a][b];
	}
	printf("%d",dp[n][n][n][n]);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int s,i;
}a[100001];
int cmp(node a,node b)
{
	return a.s<b.s;
}
int n,ans;
int main()
{
	freopen("swap.in","r",stdin);
	freopen("swap.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i].s),a[i].i=i;
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++)
	{
		int c=i%2,d=a[i].i%2;
		if(c!=d) ans++;
	}
	cout<<ans/2;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int ne,to;
}edge[110000];
int head[51000],cnt;
void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].ne=head[u];
    head[u]=cnt;
}
int n,sz[51000],mn=0x7ffffff,ans1,ans2;
void dfs(int x,int fa)
{
    sz[x]=1;
    int blance=0;
    for(int i=head[x];i;i=edge[i].ne)
    {
        int v=edge[i].to;
        if(v==fa) continue;
        dfs(v,x);
        sz[x]+=sz[v];
        blance=max(blance,sz[v]);
    }
    blance=max(blance,n-sz[x]);
    if(blance<mn||(blance==mn&&x<ans1))
    mn=blance,ans1=x;
}
int dis[51000];
void dfs1(int x,int fa)
{
    for(int i=head[x];i;i=edge[i].ne)
    {
        int v=edge[i].to;
        if(v==fa) continue;
        dis[v]=dis[x]+1;
        dfs1(v,x);
    }
}
int main()
{
//	freopen("meeting.in","r",stdin);
//	freopen("meeting.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v; 
        scanf("%d %d",&u,&v);
        add(u,v);
        add(v,u);
    }
    dfs(1,0);
    dfs1(ans1,0);
    for(int i=1;i<=n;i++)
    ans2+=dis[i];
    printf("%d %d",ans1,ans2);
    return 0;
}

#include<cstdio>
#include<algorithm>
#include<queue>
#include<string>
#include<cstring>
#include<iostream>
using namespace std;
struct node
{
	int ne,to,w;
}edge[21000];
int head[11000],cnt;
void add(int u,int v,int w)
{
	edge[++cnt].to=v;
	edge[cnt].ne=head[u];
	edge[cnt].w=w;
	head[u]=cnt;
}
int n,ml,md,dis[11000],vis[11000];
int tot[11000];
int spfa(int s)
{
	memset(dis,0x3f,sizeof(dis)); 
	queue<int>q;
	q.push(s);
	dis[s]=0;
	vis[s]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=edge[i].ne)
		{
			int v=edge[i].to,w=edge[i].w;
			if(dis[u]+w<dis[v])
			{
				dis[v]=dis[u]+w;
				if(!vis[v])
				{
					q.push(v);
					vis[v]=1;
					tot[v]++;
					if(tot[v]>n) return -1;
				}
			}
		}
	}
	if(dis[n]==0x3f3f3f3f) return -2;
	return dis[n];
}
int main()
{
	scanf("%d %d %d",&n,&ml,&md);
	for(int i=1;i<=ml;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}	
	for(int i=1;i<=md;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(v,u,-1*w);
	}
	cout<<spfa(1);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
template <class T> inline void read(T&a)
{
	T f=1;a=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){a=a*10+(s-'0');s=getchar();}
	a*=f;
} 
long long ans;
int n,s[4100000],a[4100000],l[4100000],p[4100000],top; 
int main()
{
	freopen("problem.in","r",stdin);
	freopen("problem.out","w",stdout);
	read(n);
	for(int i=1;i<=n;i++) read(a[i]);
	a[++n]=0;
	//the first element's position in the s[] which is less than a[i]
	l[1]=0;
	//position
	p[1]=1;
	//stack
	s[++top]=a[1];
	for(int i=2;i<=n;i++)
	{
		while(top&&a[i]<s[top])
		{
			ans=max((long long)s[top]*(i-l[top]-1),ans);
			top--;
		}
		s[++top]=a[i];p[top]=i;l[top]=p[top-1];
	}
	printf("%lld\n",ans);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int fr,to,w;
}edge[1200010];
int n,m,s,t,fa[100100];
int find(int x)
{
	return (fa[x]==x)?x:fa[x]=find(fa[x]);
}
inline int cmp(node a,node b)
{
	return a.w<b.w;
}
inline int kru()
{
	sort(edge+1,edge+1+m,cmp);
	for(int i=1;i<=m;i++)
	{
		
		int v=edge[i].to,u=edge[i].fr;
		int fu=find(u),fv=find(v);
		if(fu==fv) continue;
		if(fu<fv)fa[fv]=fu;
		if(fu>fv)fa[fu]=fv;
		int fs=find(s),ft=find(t);
		if(fs==ft) return edge[i].w;
	}
}
int main()
{
	freopen("first.in","r",stdin);
	freopen("first.out","w",stdout);
	scanf("%d %d %d %d",&n,&m,&s,&t);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d %d",&edge[i].fr,&edge[i].to,&edge[i].w);
	}
	cout<<kru()<<endl;
}