B - 難易度
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君はプログラミングコンテストを開く仕事をしている。
高橋君はストックしている N 個の問題から 4 問を選んでコンテストに出題する。
各問題には「難易度」という正の整数が決められており、 i 番目の問題の難易度は D_i である。
選ぶ問題は以下の 3 つの条件を満たしていなければならない。
- 2 問目の難易度は 1 問目の難易度の 2 倍以上である。
- 3 問目の難易度は 2 問目の難易度の 2 倍以上である。
- 4 問目の難易度は 3 問目の難易度の 2 倍以上である。
上の条件のもとで N 個の問題から 4 問選ぶとき、何通りの選び方があるか求めよ。
この値は非常に大きくなり得るので 1,000,000,007 (= 10^9 + 7) で割った余りを求めよ。
入力
入力は以下の形式で標準入力から与えられる
N D_1 D_2 : D_N
- 1 行目には高橋君がストックしている問題の個数 N (4 ≦ N ≦ 10^5) が与えられる。
- 2 行目からの N 行のうち i 行目には i 番目の問題の難易度を表す整数 D_i (1 ≦ D_i ≦ 10^5) が与えられる。
部分点
この問題には部分点が設定されている。
- 4 ≦ N ≦ 3,000 を満たすデータセットに正解した場合は 50 点が与えられる。
- 4 ≦ N ≦ 10^5 を満たすデータセットに正解した場合はさらに 50 点が与えられる。合計で 100 点となる。
出力
高橋君の問題の選び方の通り数を 1,000,000,007(=10^9+7) で割った余りを1行で出力せよ。 出力の末尾に改行を入れること。
入力例1
5 1 2 4 5 10
出力例1
2
1, 2, 3, 5 問目もしくは 1, 2, 4, 5 問目を選ぶことができます。
入力例2
10 11 12 13 14 15 16 17 18 19 20
出力例2
0
1 つも条件に合う選び方がないこともあります。
入力例3
20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
出力例3
94