No.754 畳み込みの和

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 72
作問者 : 37zigen37zigen / テスター : horiesinitihoriesiniti
0 ProblemId : 2175 / 出題時の順位表

問題文

関数$f(x), g(x)$があります。$f(x)=\sum_{i=0}^{\infty} a_ix^i$ かつ $g(x)=\sum_{i=0}^{\infty} b_ix^i$と表せるとします。
$a_0, a_1, ..., a_{n-1}, a_{n}$と$b_0, b_1, ..., b_{n-1}, b_{n}$を与えます。関数$f(x)g(x)=\sum_{i=0}^{\infty} c_ix^i$と置いたときの$\sum_{i=0}^{n} c_i$ を$\mod 10^9+7$で求めてください。

入力

$n$
$a_0$
$a_1$
$\vdots$
$a_{n-1}$
$a_n$
$b_0$
$b_1$
$\vdots$
$b_{n-1}$
$b_n$


$0≦n≦10^5$
$0≦a_i<10^9+7$ $(i=0,1,...,n-1,n)$
$0≦b_i<10^9+7$ $(i=0,1,...,n-1,n)$
$n,a_i,b_i$ $(i=0,1,...,n-1,n)$はすべて整数。

出力

$\sum_{i=0}^{n} c_i\mod 10^9+7$を出力してください。
最後に改行してください。

サンプル

サンプル1
入力
0
2
4
出力
8

サンプル2
入力
2
3
2
2
7
0
4
出力
61

サンプル3
入力
10
411800281
374147632
964985155
329102256
926008502
57683481
838879783
936365822
581256410
185640965
859403279
599166523
911066531
458453668
513273629
669552870
958847634
616971567
299644000
426685985
169658392
679631261
出力
386501285

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。