题目背景

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 \ (mod \ 65537$的最小正整数$x$。可以证明答案$ans$一定为正有理数，并且这样的$x$一定存在。

2 2
aa
aa

32770

3 6
i
dont
know
what
to
say

58261

提示

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

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

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

对于$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 \ (mod \ 65537)$的最小正整数$x$为$32770$。

样例#2解释：

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

注意：本题允许手动开$O2$优化以避免被卡常数，方法如下：

%:pragma GCC optimize(2)
/*程序*/