```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 20, MAXV = (1<<15)+5, Mod = 1e6+3;
int n, m, t, Size[MAXV], flwer[MAXN], enemy[MAXN], fe[MAXV];
bool f[MAXV];
string str[MAXN];
inline int check(int x, int y){
bool flag = false;
for(int i = 0; i < str[x].size(); i++){
if(str[x][i] != str[y][i] and (str[x][i] != '?' and str[y][i] != '?')) return 0;
if(str[x][i] == '?' and str[y][i] != '?') flag = true;
}
if(flag) return -1;
return 1;
}
inline int calc(int x){
int bjt[55] = {0};
for(int i = 0; i < n; i++){
if(!(x&(1<<i))) continue;
for(int j = 0; j < str[i].size(); j++)
if(str[i][j] != '?') bjt[j] = -1;
}
for(int i = 0; i < n; i++){
if(x&(1<<i)) continue;
if(fe[x]&(1<<i)) continue;
for(int j = 0; j < str[i].size(); j++){
if(bjt[j] == -1 or str[i][j] == '?') continue;
bjt[j] |= 1<<(str[i][j]-'a');
}
}
int ans = 1;
for(int i = 0; i < str[0].size(); i++)
if(bjt[i] != -1){
int cnt = 0;
for(int j = bjt[i]; j; j >>= 1) if(j&1) cnt++;
ans = (ans*(26-cnt))%Mod;
}
return ans;
}
int main(){
cin>>t;
for(int i = 0; i < 1<<15; i++)
for(int j = i; j; j >>= 1)
if(j&1) Size[i]++;
while(t--){
cin>>n>>m;
for(int i = 0; i < n; i++) cin>>str[i];
memset(flwer, 0, sizeof(flwer));
memset(enemy, 0, sizeof(enemy));
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++){
int tmp = check(i, j);
if(tmp == 1) flwer[i] |= 1<<j;
if(tmp == 0) enemy[i] |= 1<<j, enemy[j] |= 1<<i;
}
// for(int i = 0; i < n; i++) cout<<flwer[i]<<" "; cout<<endl;
// for(int i = 0; i < n; i++) cout<<enemy[i]<<" "; cout<<endl;
memset(f, false, sizeof(f));
memset(fe, 0, sizeof(fe));
f[0] = true;
for(int i = 0; i < 1<<n; i++){
if(!f[i]) continue;
for(int j = 0; j < n; j++){
if((fe[i]&flwer[j]) or (i&enemy[j])) continue;
fe[i|flwer[j]] = fe[i]|enemy[j];
f[i|flwer[j]] = true;
}
}
// for(int i = 0; i < 1<<n; i++) cout<<fe[i]<<" "; cout<<endl;
// for(int i = 0; i < 1<<n; i++) cout<<f[i]<<" "; cout<<endl;
int ans = 0;
for(int i = 0; i < 1<<n; i++){
if(Size[i] != m) continue;
if(!f[i]) continue;
ans = (ans+calc(i))%Mod;
}
printf("%d\n", ans);
}
return 0;
}
/*
1
3 2
???????
?a??j??
????aa?
*/
```
鬼畜做法，不太清楚对不对
by David_Mercury @ 2023-04-05 16:29:06
https://www.luogu.com.cn/team/57741#main
by henglizuo @ 2023-04-05 16:42:44
@[Fansitong](/user/983098) 宣传团队是吧
~~，jbl。~~
by Indufty_666 @ 2023-04-05 16:43:19
~~帮忙调下题再走吧~~
by David_Mercury @ 2023-04-05 16:45:23
~~不求帮忙看代码了来个 hack 就行力 qwq~~
by David_Mercury @ 2023-04-05 16:46:07