数え上げ入門 C編（paizaランク A 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
長さ N の数列 A = (A_1,A_2,..,A_N) が与えられます。
1 以上 N 以下の整数からなる集合 S が以下の条件を満たすとき、良い集合と呼びます。
・条件： Σ A_k (k ∈ S) が 3 の倍数
良い集合の個数の合計を 10^9 で割ったあまりを求めてください。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N
A_1 A_2 ... A_N
・ 1 行目には、整数 N が与えられます。
・ 2 行目には、数列 A が空白区切りで与えられます。
・ 入力は合計で 2 行からなり、入力値最終行の末尾に改行が１つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
良い集合の個数の合計を 10^9 で割ったあまりを求めてください。
最後は改行し、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ N ≦ 2 × 10^5
・ 0 ≦ A_i ≦ 10^9
- 入力例1
-
3
1 2 3
- 出力例1
-
4
- 入力例2
-
4
1 2 3 4
- 出力例2
-
6
- 入力例3
-
30
564111237 24508179 807717264 122157600 112578285 211179585 701310849 216157956 486804618 706097208 690359367 20968293 823401882 121856844 697182660 98078157 737036628 277271799 526540695 202567641 101379066 747627999 768579189 286201320 723820365 792083478 606123933 518907414 26871801 843436494
- 出力例3
-
73741824
