该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

注意

本题需要文件读写（chaining.in / chaining.out）。

在本题中，你可以使用以下代码，并调用 divs(a, b) 以求出 $\bm{\dfrac{b}{a}}$ 对 $\bm{10^9 + 7}$ 取模的结果。你需要保证 $\bm{1 \le a \le 10^9 + 6}$ 且 $\bm{0 \le b \le 10^9 + 6}$：

int divs(int a, int b, int p = 1e9 + 7)
{
	if (b % a == 0) return b / a;
	int x = divs(p % a, a - b % a, a);
	return (1ll * x * p + b) / a;
}

题目描述

众所周知，std::cc_hash_table 哈希表的原理是：对于每个可能的哈希值，当该哈希值的元素被插入多个时，将它们串成一个链表（新元素加在链表头部），查询时从对应哈希值的链表头部开始逐个扫描，直至找到待查询的元素，其中待查询的元素也需要扫描一次。

现有一个接受 $n$ 种哈希值的 std::cc_hash_table 哈希表，向哈希表插入 $m$ 个元素后查询 $k$ 次，插入的元素取到各哈希值的概率相等，各个元素被查询的概率也相等，所有 $m + k$ 个操作互相独立，那么 std::cc_hash_table 哈希表在 $k$ 个查询中对元素的总扫描次数的期望是多少？

答案对 $\bm{10^9 + 7}$ 取模。

输入格式

一行三个正整数 $n, m, k\ (1 \le n, m, k \le 10^9)$。

输出格式

一行一个非负整数表示答案。

答案对 $\bm{10^9 + 7}$ 取模。

样例

123 456 789

890246157

样例解释

取模前的答案是 $\dfrac{184363}{82}$。