题目描述

给出两个 $n\times n$ 的矩阵，求它们的积。

输入格式

第一行一个整数 $n$。$(1\le n\le 1500)$

第 $2\sim 2n+1$ 行，每行 $n$ 个整数，前 $n$ 行和后 $n$ 行分别表示一个矩阵。$(0\le a_{i,j}\le 500000)$

输出格式

输出 $n$ 行，每行 $n$ 个数，表示答案矩阵。答案矩阵中的每个数模 $10^9+7$ 输出。

样例

样例输入

3
2 4 1
3 0 3
6 4 2
1 0 3
4 5 2
4 8 0

样例输出

22 28 14
15 24 9
30 36 26