Description：

给定一个长度为 $ n $ 的字符串 $ S$ ，你可以在字符串 $ S $ 后再添加 $ m $ 个字符， 使得新字符串 $ T $ 所包含的不同的子序列数量尽量多。求最多的不同子序列数量。

$n+m\le 2\times10^5$

Solution：

记 $last_c$ 表示字符 $c$ 上一次出现的位置，则在后面添加 $c$ 能产生的新子序列就是在没有在 $[1,last_c)$ 中出现的子序列添上 $c$ 得到的，记 $F_i$ 表示以第 $i$ 位为结尾的新出现的不同子序列个数， $G_i$ 是 $F_i$ 前缀和，于是有 $F_i=G_{i-1}-G_{last_{c_i}-1}$ ，于是贪心的选 $last_{c_i}$ 最小的即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cstring>

using namespace std;

int n,m;

typedef long long ll;

int last[27];

#define MAXN 1000010

ll G[MAXN << 1],F[MAXN << 1],*g = G + 1,*f = F + 1;

char c[MAXN];

#define MOD 1000000007

int main()

{

	scanf("%d%d",&n,&m);

	scanf("%s",c + 1);

	int l = strlen(c + 1);

	g[-1] = f[-1] = 0;

	g[0] = f[0] = 1;

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

	{

		f[i] = (g[i - 1] - g[last[c[i] - 'a' + 1] - 1] + MOD) % MOD;

		g[i] = (g[i - 1] + f[i]) % MOD;

		last[c[i] - 'a' + 1] = i;

	}

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

	{

		int minlast = 0x3f3f3f3f,p;

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

		{

			if(last[j] < minlast)

			{

				minlast = last[j];

				p = j;

			}

		}

		f[i] = (g[i - 1] - g[minlast - 1] + MOD) % MOD;

		g[i] = (g[i - 1] + f[i]) % MOD;

		last[p] = i;

	}

	cout << g[n + l] << endl;

	return 0;

}