多项式

题号：NC207489
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

小C是CUGACM的一名萌新，从其他的学长哪里了解到，ACM比赛中数学知识是很重要的，所以他花了一段时间学习了一些数学知识。首先他研究了一下多项式展开，小C在高中学到了二项式展开：
$(x+y)^n=\sum C_{n}^{i}x^iy^{n-i}$
他在想如果括号里面是一个多项式该怎么展开呢？他想了想感觉好像有点复杂，然后简化了一下这个问题，考虑：
$(x^2+2x+(px+1)^{n})^n=\sum _{k=0}^{n^2}a_kx^k$
同时他的队友告诉他了一中神奇的数：" $\ HW$ 数"，这种数被定义为：

$abs(\mu(x))=1$ .

( $\mu$ 是莫比乌斯函数, $\ abs(x)$ 是 $\ x$ 的绝对值),

现在他让这个多项式里面的 $\ p$ 是神奇的" $\ HW$ "数，他现在想知道，对于任意的 $\ n,k,p$ , $a_k$ 是多少呢？

输入描述:

输入一行，每行三个数，。

输出描述:

输出题目中描述的。由于可能比较大，所以你只需要输出对取模之后的结果。

示例1

输入

复制

1 1 3

输出

复制

备注:

数据约束：,,。