U517211 交换游戏

[2024 年婺城区信息素养大赛](https://www.luogu.com.cn/training/675768) T2

为了新班级的凝聚力，让每个同学尽快熟悉彼此。班主任老师决定组织 $N$ 个同学在操场上进行游戏活动。老师要求这 $N$ 个同学站成一排，编号为 $1 \dots N$ 。然后给每个同学发了一张白纸，纸上每个同学自己都写下了一个小写英文字母（可能会有同学的字母重复）。 但是同学们开始排队的时候，都喜欢跟自己熟悉的同学排在一起。老师觉得这样不利于大家熟悉彼此。所以他决定，选出一对同学，让他们俩交换位置。 老师想知道，交换后，从 $1$ 到 $N$ 个人手上的字母序列排成的字符串有多少种。聪明的你来帮助老师完成这个任务！

一行，一个字符串 $S$，表示初始 $1$ 到 $N$ 个同学手上的字母的序列。

从最初的 $N$ 个人序列，交换两个人后会有多少种不同的字符串。

【样例说明】 对于样例 1，交换 $(1,2)$ 构成 `bac`，交换 $(1,3)$ 构成 `cba`，交换 $(2,3)$ 构成 `acb`，所以答案是 $3$。交换任意的两个人得到的字符串都是一样的，因此只有以一种答案。 对于样例 2，交换任意的两个人得到的字符串都是一样的，因此只有以一种答案。 【数据范围】 对于 $10\%$ 的数据，所有字母都相同。 对于 $40\%$ 的数据，$2 \le n \le 1000$。 对于 $100\%$ 的数据，$2 \le n \le 1000000$。