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で割った余りを出力してください。

制約

• \(1 \leq N \leq 10^5\)
• \(1 \leq A_i,B_i,C_i,D_i,E_i \leq 10^5\)
• 入力はすべて整数である

入力

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

N
A_1 A_2 ... A_N
B_1 B_2 ... B_N
C_1 C_2 ... C_N
D_1 D_2 ... D_N
E_1 E_2 ... 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