Description

求数组的第k小，数字数量非常多。

Input

每组数据给出n m k表示有n个数，求第k小，数组的数字由以下规则得到：

a_i = mⁱ mod  (10⁹+7), i = 1, 2, ..., n

其中 1 ≤ n, m ≤ 5 × 10⁷, 1 ≤ k ≤ n，数据保证得到的数组元素大部分互不相等。

Output

输出第k小的数

3 2 2

4