Data science is very popular now. A lot of universities have courses about it. A lot of companies have open data science positions. So it's quite important to know how to work with statistics. And this task can help you to make first step into statistics.

Lets define S as all strings of the length n consisting of letters from the some alphabet of the size a. For each string s lets define \(f(s)\) - maximum among all z-function values of the string s. Your task is calculate \(\sum_{s \in S} f(s)\) modulo \(mod\). 

You can read more about z-function on https://e-maxx-eng.appspot.com/string/z-function.html. Also in this problem we define \(z_0=0\).

Input format

First line of input contains three space separated integers n, a and \(mod\) (\(1 \leq n \leq 22\), \(1 \leq a \leq 10^9\), \(1 \leq mod \leq 10^9\)).

Note that \(mod\) may be composite.

Output format

Print the single integer \(\sum_{s \in S} f(s)\) modulo \(mod\).