Shortest Unique Prefix

题目描述

Let $S = S_1 S_2 \cdots S_n$ be a string of length $n$. For indices $1 \le l \le r \le n$, let $S[l..r]$ denote the substring $S_lS_{l+1}\cdots S_r$.

For $1 \le l \le n$, the prefix $S[1..l]$ is said to be unique if it occurs in $S$ only as a prefix; that is, there is no index $p$ with $2 \le p \le n-l+1$ satisfying $S[p..p+l-1] = S[1..l]$.

The prefix $S[1..n] = S$ is always unique, so every string has at least one unique prefix. Define the uniqueness $u(S)$ of $S$ as the length of its shortest unique prefix,

$$u(S) = \min\{\, l : 1 \le l \le n,\ S[1..l]\ \text{is unique} \,\},$$

so that $1 \le u(S) \le n$ for every $S$.

Given three integers $n$, $k$, and $p$, consider the $k^{n}$ strings of length $n$ over an alphabet of $k$ distinct symbols. Compute

$$\left( \sum_{S} u(S) \right) \bmod p,$$

where the sum is taken over all $k^{n}$ such strings.

输入格式

A single line containing three integers $n$, $k$, and $p$.

$1 \le n \le 80$, $1 \le k \le 100$, $10^{8} \le p \le 10^{9}$. It is not guaranteed that $p$ is prime.

输出格式

A single integer: the value of $\bigl(\sum_{S} u(S)\bigr) \bmod p$.

样例输入 #1

2 3 998244353

样例输出 #1

12

样例输入 #2

3 1 998244353

样例输出 #2

3

样例输入 #3

20 5 998244353

样例输出 #3

311627017