题目背景

zhoutb2333学习了哈希算法，他于是去统计给定一些字符串，其中有多少个本质不同的字符串。

但是zhoutb2333突发奇想，如果哈希采用的$base$每次随机，那么结果会变成什么样呢？

辣鸡出题人又出锅了！subtask3的数据有问题，现在统一将模数改为65537

题目来源：zhoutb2333

题目描述

他通过某种办法，获得了一个函数：int Rand(int x)，它会等概率地返回一个 $[0,x)$ 中的整数。

他写下了这样的代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int x=10,maxn=35,maxlen=16010;
ll HASH[maxn];
const ll p=65537;
char str[maxlen];
ll Hash(){
    int base=Rand(x);
    ll ret=0;
    for(int i=1;str[i];i++)
        ret=(ret*base+str[i]-'a'+1)%p;
    return ret;
}
int main(){
    int ans=0,n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%s",str+1),HASH[i]=Hash();
    sort(HASH+1,HASH+n+1);
    HASH[0]=-1;
    for(int i=1;i<=n;i++)
        ans+=(HASH[i]!=HASH[i-1]);
    printf("%d\n",ans);
    return 0;
}

zhoutb2333 想问你，给定一些字符串和参数 $x$，答案 $ans$ 的期望是多少呢？

$65537= 2^{16}+1$ 是质数

参数 $x$ 在这个程序中是确定的 $10$，但是每次输入会给定。

输入格式

第一行三个整数 $x,N$，表示 $base$ 生成的参数和字符串的个数

接下来 $N$ 行每行一个字符串，字符串仅由小写字母组成。

输出格式

一行一个小数，表示答案 $ans$ 的期望，模 $65537$ 输出。

即：如果你的答案为 $\frac{q}{p}$（$\gcd (p,q)=1$），那么输出使得 $px \equiv q \pmod {65537}$ 的最小正整数 $x$。可以证明答案 $ans$ 一定为正有理数，并且这样的 $x$ 一定存在。

2 2
aa
aa

32770

3 6
i
dont
know
what
to
say

58261

提示

本题由 $3$ 个 $\text{subtask}$ 组成，设 $M$ 为这 $N$ 个字符串中，每个字符串长度的最大值。

对于 $\text{subtask} \ 1$：$1 \le N \le 8 , M \le 10,x \le 4$，分值为 $20$，时间限制为 $1s$。

对于 $\text{subtask} \ 2$：$1 \le N \le 30 , M \le 500,x \le 500$，分值为 $50$，时间限制为 $1s$。

对于 $\text{subtask} \ 3$：$1 \le N \le 5 , M \le 16000,x \le 16000$，分值为 $30$，时间限制为 $4.5s$。

样例 #1 解释：

参数 $x=2$，那么可能的哈希 $base$ 为 $0,1$。

如果哈希第一个 aa 采用的 $base$ 和第二个 aa 的 $base$ 相同，那么答案为 $1$。

如果两个 $base$ 不相同，那么答案为 $2$。

分析发现这两种情况发生的概率相同，都是 $\frac{1}{2}$，那么答案 $ans$ 的期望为 $1 * \frac{1}{2} + 2 * \frac{1}{2}=\frac{3}{2}$。使得 $2x \equiv 3 \ \pmod {65537}$ 的最小正整数 $x$ 为 $32770$。

样例 #2 解释：

求得答案为 $\frac{53}{9}$。使得 $9x \equiv 53 \ \pmod {65537}$ 的最小正整数 $x$ 为 $58261$。