問題一覧 > 通常問題

No.754 畳み込みの和

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 232
作問者 : 37zigen37zigen / テスター : 👑 horiesinitihoriesiniti
4 ProblemId : 2175 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-09-30 16:23:35

問題文

関数$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

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。