首先先观察到一个非常浅显的性质：就是一个位置在序列中不是第一次出现，那么到这个位置的时候打出这个字符需要恰好一次按键，这是因为我们肯定在打出第一次出现这个字符的位置的时候已经知道哪个键对应这个字符了，到那个位置的时候直接敲一下就 ok 了。
也就是我们只用关心这个序列中出现了多少种不同的数，设为 \(A\)，并假设序列就是 \(0,1,2,\cdots,A-1\)。那么考虑一次从啥也不知道到打出这个句子出来经过怎么样的过程：显然是你先随机乱按，按出一个与原序列的 \(\text{LCP}=l_1\)，长度为 \(l_1+l_2\) 的序列，然后突然按到了 Backspace，然后再把剩余 \(l_2-1\) 个与 LCP 不符合的字符删掉，然后再确定剩余的数字键，策略是如果下一个字符你在之前猜 Backspace 的过程中就确定了，那么直接按出来，否则乱猜一个键，如果符合就继续，不符合就按 BACKSPACE 再猜剩下的。当然比较特殊的一种情况是运气比较好连 Backspace 都不知道就直接打出了原句子，还有一种可能是 \(l_2=0\)，此时按下 BACKSPACE 之后需要把删掉的那个字符补回来。
本人思考时候一个比较 naive 的思路是你枚举这个 \(l_1,l_2\)，这样你大概可以得到一个 \(n^4\) 的做法，由于比较垃圾就不再赘述。考虑怎么优化到 \(n^2\)：摊贡献。在探索 Backspace 的过程中，我们考虑将 \(l_2\) 的贡献摊到按下错误字符的 DP 过程中计算。在打出剩余部分的过程中，如果一个字符之前我们已经确定了它的位置，那么我们就将这个贡献摊到发现键盘上哪个键对应这个字符的时候计算。这样我们考虑设三个 \(dp\) 数组：
- \(f_{i,j}\) 表示已经知道了 Backspace 键是什么，还剩 \(i\) 个 \([0,A-1]\) 中的键没有确定，\(j\) 个 \([A,m-1]\) 中的键没有确定的期望次数。
- \(g_{i,j}\) 表示还没知道 Backspace 键是什么，目前 \(l_2\ne 0\)，还剩 \(i\) 个 \([0,A-1]\) 中的键没有确定，\(j\) 个 \([A,m-1]\) 中的键没有确定的期望次数。
- \(h_{i,j}\) 表示还没知道 Backspace 键是什么，目前 \(l_2=0\)，还剩 \(i\) 个 \([0,A-1]\) 中的键没有确定，\(j\) 个 \([A,m-1]\) 中的键没有确定的期望次数。
考虑转移，先考虑 \(f\) 的转移，分三种情况：
- 按下的键就是下一个字符，概率为 \(\dfrac{1}{i+j}\)，贡献 \(f_{i-1,j}+1\)。
- 按下的键不是下一个字符，但是是另一个 \([0,A-1]\) 中没有被确定的字符，概率为 \(\dfrac{i-1}{i+j}\)，贡献 \(f_{i-1,j}+3\)，这个 \(3\) 是因为我按下了一个键，Backspace 把它去掉，下次再遇到时还需要一次（摊贡献）。
- 按下的键是一个 \([A,m-1]\) 中没有被确定的字符，概率为 \(\dfrac{j}{i+j}\)，贡献 \(f_{i,j-1}+3\)。
再考虑 \(g\) 的转移，分三种情况：
- 按下的键是 Backspace，概率为 \(\dfrac{1}{i+j+1}\)，贡献 \(f_{i,j}+1\)。
- 按下的键是一个 \([0,A-1]\) 中没被确定的字符，概率为 \(\dfrac{i}{i+j+1}\)，贡献 \(g_{i-1,j}+3\)，这个 \(3\) 是因为我按下一个键，在确定 Backspace 后要把这个字符删掉，在后面我遇到这个字符时又要按一次。
- 按下的键是一个 \([A,m-1]\) 中没被确定的字符，概率为 \(\dfrac{j}{i+j+1}\)，贡献 \(g_{i,j-1}+2\)。
最后考虑 \(h\)，分四种情况：
- 按下的键是下一个字符，概率为 \(\dfrac{1}{i+j+1}\)，贡献 \(h_{i-1,j}+1\)。
- 按下的键不是下一个字符但是是某个 \([0,A-1]\) 中没被确定的字符，概率为 \(\dfrac{i-1}{i+j+1}\)，贡献 \(g_{i-1,j}+3\)。
- 按下的键是某个 \([A,m-1]\) 中没被确定的字符，概率为 \(\dfrac{j}{i+j+1}\)，贡献 \(g_{i,j-1}+2\)
- 按下的键是 Backspace，概率为 \(\dfrac{1}{i+j+1}\)，贡献 \(f_{i,j}+2\)，\(2\) 是因为我要把删掉的字符补回来。
于是做完了，复杂度 \(O(n^2)\)。
const int MAXN=1e3+1;
const int MOD=1e9+7;
int n,m,A,B,f[MAXN+5][MAXN+5],g[MAXN+5][MAXN+5],h[MAXN+5][MAXN+5],inv[MAXN+5];
int main(){
scanf("%d%d",&n,&m);set<int>st;
for(int i=(inv[0]=inv[1]=1)+1;i<=MAXN;i++)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
for(int i=1,x;i<=n;i++)scanf("%d",&x),st.insert(x);
A=st.size();B=m-A;
for(int i=1;i<=A;i++)for(int j=0;j<=B;j++){
f[i][j]=1ll*(i-1)*inv[i+j]%MOD*(f[i-1][j]+3)%MOD;
f[i][j]=(f[i][j]+1ll*inv[i+j]*(f[i-1][j]+1))%MOD;
if(j)f[i][j]=(f[i][j]+1ll*inv[i+j]*j%MOD*(f[i][j-1]+2))%MOD;
}
for(int i=0;i<=A;i++)for(int j=0;j<=B;j++){
g[i][j]=1ll*inv[i+j+1]*f[i][j]%MOD;
if(i)g[i][j]=(g[i][j]+1ll*inv[i+j+1]*i%MOD*(g[i-1][j]+3))%MOD;
if(j)g[i][j]=(g[i][j]+1ll*inv[i+j+1]*j%MOD*(g[i][j-1]+2))%MOD;
}
for(int i=1;i<=A;i++)for(int j=0;j<=B;j++){
h[i][j]=1ll*inv[i+j+1]*(h[i-1][j]+1)%MOD;
h[i][j]=(h[i][j]+1ll*(i-1)*inv[i+j+1]%MOD*(g[i-1][j]+3))%MOD;
if(j)h[i][j]=(h[i][j]+1ll*j*inv[i+j+1]%MOD*(g[i][j-1]+2))%MOD;
h[i][j]=(h[i][j]+1ll*inv[i+j+1]*(f[i][j]+2))%MOD;
}
int res=n-A;
res=(res+1ll*inv[m+1]*(f[A][B]+1))%MOD;
res=(res+1ll*inv[m+1]*(h[A-1][B]+1))%MOD;
res=(res+1ll*inv[m+1]*(A-1)%MOD*(g[A-1][B]+3))%MOD;
res=(res+1ll*inv[m+1]*B%MOD*(g[A][B-1]+2))%MOD;
printf("%d\n",res);
return 0;
}