Description：

给定 $n$ 个字符串，将他们划分成若干个块使得块内字符串之间的编辑距离 $<$ 块内与块外所有其他字符串的编辑距离，问方案数。

$1\le T \le 20$ $1\le N \le 400$

Solution：

编辑距离等于距离和减最长公共子序列长。

将字符串看作点，则得到了一张完全图。块内点之间的距离一定较小，于是把边排序，像 $kruskal$ 一样加边并用并查集维护连通性，设 $f[k]$ 为 $k$ 所在联通块划分的方案数，对于一条边，要么不存在于最后的划分方案中，要么将两个联通块合并为一个大联通块，则合并边 $(u,v)$ 时， $f[merge(u,v)]=f[u]\times f[v]$ ，代表不把他们划到一个联通块里，然后枚举边检查是否符合块内字符串之间的编辑距离 $<$ 块内与块外所有其他字符串的编辑距离，如果符合，说明可以将他们划为一个大联通块。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MOD 1000000007ll

#define INF 0x3f3f3f3f

int testcases;

int n;

#define MAXN 401

#define MAXM (MAXN * (MAXN - 1) / 2)

struct edge

{

	int u,v,w;

}e[MAXM];

int edgenum = 0;

void add(int a,int b,int c)

{

	++edgenum;

	e[edgenum].u = a;

	e[edgenum].v = b;

	e[edgenum].w = c;

	return;

}

#define MAXL 21

char s[MAXN][MAXL];

int f[MAXL][MAXL];

int dis(int a,int b)

{

	int l1 = strlen(s[a] + 1),l2 = strlen(s[b] + 1);

	memset(f,0,sizeof(f));

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

	{

		for(int j = 1;j <= l2;++j)

		{

			f[i][j] = max(f[i - 1][j],f[i][j - 1]);

			if(s[a][i] == s[b][j])

			{

				f[i][j] = max(f[i][j],f[i - 1][j - 1] + 1);

			}

		}

	}

	return l1 + l2 - 2 * f[l1][l2];

}

long long g[MAXN];

bool cmp(edge a,edge b){return a.w < b.w;}

int fa[MAXN];

int find(int x){return (x == fa[x] ? x : fa[x] = find(fa[x]));}

bool check(int k)

{

	int maxf = -INF,minf = INF;

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

	{

		if(find(e[i].u) == k && find(e[i].v) == k)

		{

			maxf = max(maxf,e[i].w);

		}

		if((find(e[i].u) == k && find(e[i].v) != k) || (find(e[i].v) == k && find(e[i].u) != k))

		{

			minf = min(minf,e[i].w);

		}

	}

	return (maxf < minf);

}

void work()

{

	edgenum = 0;

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)g[i] = 1;

	for(int i = 1;i <= n;++i)fa[i] = i;

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

	{

		scanf("%s",s[i] + 1);

	}

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

	{

		for(int j = i + 1;j <= n;++j)

		{

			add(i,j,dis(i,j));

		}

	}

	sort(e + 1,e + 1 + edgenum,cmp);

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

	{

		int p = find(e[i].u),q = find(e[i].v);

		if(p == q)continue;

		g[q] = g[p] * g[q] % MOD;

		fa[p] = q;

		if(check(q))g[q] = (g[q] + 1) % MOD;

	}

	cout << g[find(1)] << endl;

	return;

}

int main()

{

	scanf("%d",&testcases);

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

	{

		work();

	}

	return 0;

}