Problem Background

zhoutb2333 has learned about hash algorithms and decided to count how many distinct strings exist among a given set of strings.

However, zhoutb2333 had a sudden thought: what if the base used for hashing was random each time? What would the results look like?

The problem setter messed up again! The modulus for subtask 3 has been uniformly changed to 65537.

Source: zhoutb2333

Problem Description

He obtained a function: int Rand(int x), which returns an integer uniformly at random from the range [0, x).

He wrote the following code:

#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 wants to know, given a set of strings and the parameter \( x \), what is the expected value of \( ans \)?

\( 65537 = 2^{16} + 1 \) is a prime number

The parameter \( x \) in this program is fixed at 10, but it will be given as input each time.

Input Format

The first line contains three integers \( x \) and \( N \), representing the parameter for generating the base and the number of strings, respectively.

The next \( N \) lines each contain a string consisting only of lowercase letters.

Output Format

Output a single line with a decimal number representing the expected value of \( ans \), modulo 65537.

That is, if your answer is \( \frac{q}{p} \) (where \( gcd(p, q) = 1 \)), output the smallest positive integer \( x \) such that \( px \equiv q \ (mod \ 65537) \). It can be proven that the answer \( ans \) is always a positive rational number, and such an \( x \) always exists.

Sample Input and Output

Sample Input #1

2 2
aa
aa

Sample Output #1

32770

Sample Input #2

3 6
i
dont
know
what
to
say

Sample Output #2

58261

Notes

This problem consists of 3 subtasks. Let \( M \) be the maximum length of the strings among the \( N \) strings.

For subtask 1: \( 1 \le N \le 8, M \le 10, x \le 4 \), worth 20 points, time limit is 1 second.

For subtask 2: \( 1 \le N \le 30, M \le 500, x \le 500 \), worth 50 points, time limit is 1 second.

For subtask 3: \( 1 \le N \le 5, M \le 16000, x \le 16000 \), worth 30 points, time limit is 4.5 seconds.

Explanation for Sample #1:

The parameter \( x = 2 \), so the possible hash bases are \( 0 \) and \( 1 \).

If the hash base used for the first aa is the same as the second aa, the answer is 1.

If the two bases are different, the answer is 2.

Analyzing these cases, we find that both occur with equal probability, \( \frac{1}{2} \). Therefore, the expected value of \( ans \) is \( 1 \times \frac{1}{2} + 2 \times \frac{1}{2} = \frac{3}{2} \). The smallest positive integer \( x \) such that \( 2x \equiv 3 \ (mod \ 65537) \) is 32770.

Explanation for Sample #2:

The answer obtained is \( \frac{53}{9} \). The smallest positive integer \( x \) such that \( 9x \equiv 53 \ (mod \ 65537) \) is 58261.

Note: This problem allows manual O2 optimization to avoid being stuck by constant factors, as follows:

%:pragma GCC optimize(2)
/* program */

见题面 Input 部分

见题面 Output 部分