問題文
高桥的工作是举办编程比赛。
高桥君有货。 来自 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