

Time Limit: 2 sec / Memory Limit: 256 MiB
配点 : 点
問題文
すぬけくんは長さ の数列 をもらいました。
すぬけくんは を自由に並び替えたあと、 を使って新しい数列 を作りました。 は以下に示されるような長さ の数列です。
- の中央値
- の中央値
- の中央値
- の中央値
としてありうる数列の数を modulo で求めてください。
制約
- は整数
入力
入力は以下の形式で標準入力から与えられる。
出力
答えを出力せよ。
入力例 1Copy
2 1 3 2
出力例 1Copy
3
としてありうる数列は の 通りです。これらはそれぞれ から作ることが可能です。
入力例 2Copy
4 1 3 2 3 2 4 3
出力例 2Copy
16
入力例 3Copy
15 1 5 9 11 1 19 17 18 20 1 14 3 3 8 19 15 16 29 10 2 4 13 6 12 7 15 16 1 1
出力例 3Copy
911828634
で割ったあまりを求めてください。
Score : points
Problem Statement
Snuke received an integer sequence of length .
He arbitrarily permuted the elements in , then used it to construct a new integer sequence of length , as follows:
- the median of
- the median of
- the median of
- the median of
How many different sequences can be obtained as ? Find the count modulo .
Constraints
- are integers.
Input
Input is given from Standard Input in the following format:
Output
Print the answer.
Sample Input 1Copy
2 1 3 2
Sample Output 1Copy
3
There are three sequences that can be obtained as : , and . Each of these can be constructed from , and , respectively.
Sample Input 2Copy
4 1 3 2 3 2 4 3
Sample Output 2Copy
16
Sample Input 3Copy
15 1 5 9 11 1 19 17 18 20 1 14 3 3 8 19 15 16 29 10 2 4 13 6 12 7 15 16 1 1
Sample Output 3Copy
911828634
Print the count modulo .