問題文
N 次多項式 A(x)=aNxN+⋯+a1x+a0 と、
M 次多項式 B(x)=bMxM+⋯+b1x+b0 が与えられます。
A(x) を B(x) で割った商 Q(x) と 余り R(x) を計算してください。
制約
- 0≤N,M≤100
- 0≤ai,bj≤109
- aN,bM,B(x)=0
- 入力はすべて整数
入力
N M
a_N ... a_1 a_0
b_M ... b_1 b_0
出力
1 行目に Q(x) と R(x) の次数、 2 行目に Q(x) の係数を 109+7 で割ったあまり、 3 行目に R(x) の係数を 109+7 で割ったあまりを次数が高い順に出力してください。
K L
q_K ... q_1 r_0
r_L ... r_1 r_0
入出力例1
x2+3x+3 を x+2 で割ると、商は x+1 、 余りは 1 になります。
入出力例2
入力例2
2 1
1 0 1000000006
1 1
x2−1 を x+1 で割ると、商は x−1 、 余りは 0 になります。
入出力例3
出力例3
1 0
500000004 250000003
750000006
x2+3x+2 を 2x+1 で割ると、 商は 21x+45 、 余りは 43 になります。