秋祭 | 静岡高校工学部


卬高杯

I問題 - TsuruNoTsurugi Easter

実行時間制限: 2 sec / メモリ制限: 1024 MB

問題文

静岡高校では、近年高まりを見せている鶴の剣信仰の機運に合わせ、鶴の剣復活祭を執り行うことになりました。
C氏は鶴の剣復活の儀式に使う祭壇を作ろうとしています。
祭壇は鶴の剣のブロマイド、上部、中部、下部、土台の5つのカテゴリーのパーツ一つずつから作れます。
祭壇の5つのパーツはそれぞれ`N`個ずつあります。 `i`個目の鶴の剣のブロマイドのサイズは`A_i`、 `i`個目の上部のパーツのサイズは`B_i`、 `i`個目の中部のパーツのサイズは`C_i`、 `i`個目の下部のパーツのサイズは`D_i`、 `i`個目の土台のパーツのサイズは`E_i`です。
祭壇は、上部のパーツのサイズは鶴の剣のブロマイドのサイズより真に大きく、 中部のパーツのサイズは上部のパーツのサイズより真に大きく、 下部のパーツのサイズは中部のパーツのサイズより真に大きく、 土台のパーツのサイズは下部のパーツのサイズより真に大きくなければなりません。逆に、この条件を満たす任意の 5 つのピースを組み合わせて祭壇を作ることができます。
C氏が作ることのできる祭壇は何種類あるのでしょうか。 ただし二つの祭壇が異なるとは、鶴の剣のブロマイド、上部、中部、下部、土台に使われるパーツのうち 少なくとも一つが異なることを言います。 また答えは非常に大きくなる可能性があるので、127237991で割った余りを出力してください。

制約

入力

入力は以下の形式で標準入力から与えられる。

`N`
`A_1 \quad A_2 \quad \cdots \quad A_N`
`B_1 \quad B_2 \quad \cdots \quad B_N`
`C_1 \quad C_2 \quad \cdots \quad C_N`
`D_1 \quad D_2 \quad \cdots \quad D_N`
`E_1 \quad E_2 \quad\cdots \quad E_N`

出力

C氏の作ることのできる祭壇の数を素数127237991で割った値を整数で出力せよ。

入力例1

2
1 5
2 7
3 8
4 9
114 514

出力例1

10

次の10種類の祭壇が考えられます

  • 鶴の剣のブロマイドに 1 個目上部に 1 個目、中部に 1 個目、下部に 1 個目、土台に 1 個目のパーツを使った祭壇
  • 鶴の剣のブロマイドに 1 個目上部に 1 個目、中部に 1 個目、下部に 1 個目、土台に 2 個目のパーツを使った祭壇
  • 鶴の剣のブロマイドに 1 個目上部に 1 個目、中部に 1 個目、下部に 2 個目、土台に 1 個目のパーツを使った祭壇
  • 鶴の剣のブロマイドに 1 個目上部に 1 個目、中部に 1 個目、下部に 2 個目、土台に 2 個目のパーツを使った祭壇
  • 鶴の剣のブロマイドに 1 個目上部に 1 個目、中部に 2 個目、下部に 2 個目、土台に 1 個目のパーツを使った祭壇
  • 鶴の剣のブロマイドに 1 個目上部に 1 個目、中部に 2 個目、下部に 2 個目、土台に 2 個目のパーツを使った祭壇
  • 鶴の剣のブロマイドに 1 個目上部に 2 個目、中部に 2 個目、下部に 2 個目、土台に 1 個目のパーツを使った祭壇
  • 鶴の剣のブロマイドに 1 個目上部に 2 個目、中部に 2 個目、下部に 2 個目、土台に 2 個目のパーツを使った祭壇
  • 鶴の剣のブロマイドに 2 個目上部に 2 個目、中部に 2 個目、下部に 2 個目、土台に 1 個目のパーツを使った祭壇
  • 鶴の剣のブロマイドに 2 個目上部に 2 個目、中部に 2 個目、下部に 2 個目、土台に 2 個目のパーツを使った祭壇

    • 入力例2

    4
    1 1 1 1
    2 2 2 2
    3 3 3 3
    4 4 4 4
    5 5 5 5

    出力例2

    1024

    同じ種類のパーツが入っていることもあります。

    入力例3

    114
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
    2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
    3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
    4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
    5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5

    出力例3

    41209183

    出力がint型の範囲に収まらないこともあります。

    入力例4

    1
    29
    15
    51
    1000
    92

    出力例4

    0

    祭壇を一種類も作れないこともあります

    入力例5

    5
    32 65 42 14 29
    15 114 90 75 74
    28 17 99 514 61
    55 38 21 41 1000
    92 32 72 36 1919

    出力例5

    63
    提出はここから