题目描述

由于不定积分比较麻烦，所以你只需要输出定积分：

$\int_0^{x_0}{(x+s)^n(x+t)^mdx}$

$n,m$ 也不可能太大，所以 ckr 要求 $1 \le n,m \le N$。

由于 ckr 现在还处于探索阶段，每一个数据都是很重要的，所以你需要对每个 $1 \le n,m \le N$ 且 $n,m$ 是完全平方数求出答案。

由于答案可能很大，你只需要求出答案关于 2147483647 取模后的值。

输入格式

输入一行四个整数 $N, s, t, x_0$。

输出格式

第 $i$ 行第 $j$ 个整数表示 $n = i^2, m = j^2$ 的答案。

样例1输入

4 3 7 1

样例1输出

1431655791 1932746596
930577433 1950302041

样例2输入

9 432626436 222345443 0

样例2输出

0 0 0
0 0 0
0 0 0

样例3输入

9 233333 233333 666666

样例3输出

1703229151 2113117123 1350295746
2113117123 1384164355 1123817829
1350295746 1123817829 456733368

数据范围

$0 \le s, t, x0 < 2147483647, 1 \le N \le 10^5$。