UOJ Logo

NOI.AC

1S 256MB
Statistics

题目描述

小h在种蔬菜。

作为一位理论计算机科学家,小h对于种菜有一套独特的理解。

小h打算在接下来的$n$天里每天在心里随机一个$\left[0,Q\right]$之间的随机数。如果这个数$>0$,那么他就会去田里劳动。假设这是他第$i$次劳动,他的心情就会变好$i^k$。

现在小h想要知道他的心情期望变好多少呢?

请输出这个期望乘上$(Q+1)^n$的值,答案对$10^9+7$取模。

输入格式

从标准输入读入数据。

一行三个正整数$n,k,Q$,意义如题面所示。

输出格式

输出到标准输出。

一行一个整数,表示答案对$10^9+7$取模的值。

样例

输入

2 2 2

输出

24

子任务

$1\le n \le 10^9,1\le Q\le 10^9,0\le k \le 3\times 10^3$

对于$10\%$的数据 : $n\le 2$

对于另外$20\%$的数据 : $n\le 20$

对于另外$10\%$的数据 : $k=0$

对于另外$20\%$的数据 : $n\le 10^6$

对于$100\%$的数据 : 无特殊性质。

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载