AT_code_festival_2017_qualc_f Three Gluttons

[problemUrl]: https://atcoder.jp/contests/code-festival-2017-qualc/tasks/code_festival_2017_qualc_f $ 3 $ 人の男性 A, B, C が一緒に寿司を食べることになりました。 最初、$ N $ 種類の寿司が $ 1 $ 個ずつあります。 寿司には $ 1 $ から $ N $ まで番号が振られています。 ただし、$ N $ は $ 3 $ の倍数とします。 $ 3 $ 人はそれぞれ寿司に対して好き嫌いの順位付けを持っています。 A の順位付けは、$ 1 $ から $ N $ までの順列 $ (a_1,\ ...,\ a_N) $ で表されます。 各 $ i $ ($ 1\ \leq\ i\ \leq\ N $) について、A が $ i $ 番目に好きな寿司は寿司 $ a_i $ です。 同様に、B および C の順位付けは、$ 1 $ から $ N $ までの順列 $ (b_1,\ ...,\ b_N) $ および $ (c_1,\ ...,\ c_N) $ で表されます。 寿司がすべて無くなるか、喧嘩が起こる (後述) まで、$ 3 $ 人は次の行動を繰り返します。 - A, B, C はそれぞれ、残りの寿司のうち最も好きな寿司を見つける。 これらをそれぞれ寿司 $ x $, $ y $, $ z $ とする。 $ x $, $ y $, $ z $ がすべて相異なるならば、A, B, C はそれぞれ寿司 $ x $, $ y $, $ z $ を食べる。 そうでないならば、$ 3 $ 人は殴り合いの喧嘩を始める。 A および B の順位付け $ (a_1,\ ...,\ a_N) $ および $ (b_1,\ ...,\ b_N) $ が与えられます。 C の順位付け $ (c_1,\ ...,\ c_N) $ のうち、$ 3 $ 人が喧嘩を始めることなく寿司をすべて食べ切れるようなものは、何通りあるでしょうか？ $ 10^9+7 $ で割った余りを求めてください。

N/A

N/A

### 制約 - $ 3\ \leq\ N\ \leq\ 399 $ - $ N $ は $ 3 $ の倍数である。 - $ (a_1,\ ...,\ a_N) $ および $ (b_1,\ ...,\ b_N) $ は $ 1 $ から $ N $ までの順列である。 ### Sample Explanation 1 $ (c_1,\ c_2,\ c_3)\ =\ (3,\ 1,\ 2),\ (3,\ 2,\ 1) $ の $ 2 $ 通りです。 どちらの場合も、A, B, C はそれぞれ寿司 $ 1 $, $ 2 $, $ 3 $ を食べ、寿司がすべて無くなります。 ### Sample Explanation 2 $ (c_1,\ c_2,\ c_3) $ がどのような順列であっても、A と B はともに寿司 $ 1 $ を食べようとするので、喧嘩が起こります。 ### Sample Explanation 3 例えば $ (c_1,\ c_2,\ c_3,\ c_4,\ c_5,\ c_6)\ =\ (5,\ 1,\ 2,\ 6,\ 3,\ 4) $ の場合、まず A, B, C はそれぞれ寿司 $ 1 $, $ 2 $, $ 5 $ を食べ、次に A, B, C はそれぞれ寿司 $ 3 $, $ 4 $, $ 6 $ を食べ、寿司がすべて無くなります。