RUN 的魔剑社长 Cocoa 获得了一把名为 Armageddon 的新魔剑。为了最大化其威力，Cocoa 打算强化它。

具体来说，魔剑的威力由其长度 $x$、附魔等级 $y$ 和光辉度 $z$ 决定，公式如下：

$$\frac{x(x+1)}{2} \cdot \frac{y(y+1)}{2} \cdot a^z$$

其中 $x, y, z$ 是非负整数。这里，$a$ 是在锻造 Armageddon 时确定的固定常数。初始时，$x, y, z$ 均初始化为 0。

Cocoa 可以投入她的魔力来改良这把剑。每消耗 1 点魔力，她可以将 $x$、$y$ 或 $z$ 中的任意一个增加 1。

对于每个 $k = 1, 2, \dots, n$，求如果 Cocoa 恰好使用 $k$ 点魔力来强化魔剑，魔剑可能达到的最大威力。

输入格式

第一行包含三个由空格隔开的整数 $p$、$q$ 和 $n$，其中 $a = p/q$。

输出格式

在单行中输出 $n$ 个值，用空格隔开。

对于第 $i$ 个值，输出 $s \times t^{-1} \pmod{10^9 + 7}$，其中 $s/t$ 是表示在恰好投入 $i$ 点魔力后可能达到的最大威力的既约分数。

数据范围

• $1 \le p, q, n \le 10^5$

样例

输入样例 1

1 1 10

输出样例 1

0 1 3 9 18 36 60 100 150 225

输入样例 2

2 1 10

输出样例 2

0 1 3 9 18 36 72 144 288 576

输入样例 3

100000 1 5

输出样例 3

0 1 100000 999999937 993000007

说明

RUN 中并没有魔剑社长。