← 返回题目列表

AtCoder · arc043_b

B. 难度

中文机器翻译题面 查看原题

問題文

高桥的工作是举办编程比赛。

高桥君有货。 来自 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

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