暂无测试数据。

给定一个数列 $\{a_n\}$，满足 $a_1=0,a_2=k(\leq 10^9)$，当 $i> 2$ 时，$a_{i}=ia_{i-1}+ia_{i-2}$。

对于两个正整数 $m,n$，求 $|a_{2m+1}-A_{2m+2}^{2m-2n}a_{2n+1}|$ 对 $10^9+7$ 取模的值。

其中对于 $A_x^y$ 的计算方法为：

$A_x^y = x(x-1)(x-2) \cdots (x-y+1) = \frac{x!}{(x-y)!}$。

$x! = 1 \times 2 \times 3 \times \cdots \times x$。

$|x|$ 表示 $x$ 的绝对值，例如 $|-2| = 2, |3| = 3$。

输入格式

三个正整数 $m,n,k$ 。

输出格式

输出共一行，一个整数，表示答案。

数据范围

对于 $30\%$ 的数据，保证 $n, m \leq 10^5$ 。

对于 $100\%$ 的数据，保证满足 $n<m<10^{18}$ 且 $m-n<10^7$ 。

3 2 1

7