[R38F]魔塔 - 代码源竞赛平台

时空限制

4S/512M

题目描述

jiangly 发现了一座古老的魔塔，塔内有 $n$ 个珠子，第 $i$ 个珠子具有不平衡度 $a_i$。

jiangly 可以从这 $n$ 个珠子中按原顺序选取若干个珠子来搭建一座新塔。如果选出的珠子不平衡度依次为 $v_1, v_2, \dots, v_k$，则整座塔的总不平衡度计算公式为：

$$v_1^{(v_2^{(\dots^{v_k})})}$$

（注：运算顺序为从右上向左下进行，即 $v_1 \wedge (v_2 \wedge (\dots \wedge v_k))$）。

为了保证魔塔稳定，塔的总不平衡度不能超过给定的阈值 $X$。 求有多少种不同的选取珠子的方案，使得塔稳定。两个方案被认为是不同的，当且仅当选取的珠子下标集合不同。

由于答案可能很大，请输出答案对 $666666666$ 取模的结果。

格式

输入格式

第一行包含两个整数 $n, X$，分别表示珠子的总数和不平衡度的最大阈值。

第二行包含 $n$ 个整数 $a_i$，表示每个珠子的不平衡度。

输出格式

输出一个整数，表示方案数对 $666666666$ 取模后的结果。

样例

样例输入 #1

5 20
2 3 2 3 2

样例输出 #1

15

样例解释 #1

方案解释：

• 选取 $2$ 个及以下珠子的方案：除了组合 $(3, 3)$ 不合法（因为 $3^3=27 > 20$）外，其余均合法。
• 选取 $3$ 个及以上珠子的方案：只有选取第 $1$、$3$、$5$ 个珠子（值为 $2$, $2$, $2$）合法，因为 $2^{(2^2)} = 16 \le 20$。 总方案数为 $15$。

样例输入 #2

4 6553665536
2 2 2 2

样例输出 #2

15

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$	$a_i$
$1$	$10$	$15$	$\ge 2$
$2$	$15$	$40$
$3$	$20$	$10^6$	$\ge 4$
$4$	$25$		$\ge 3$
$5$	$30$		$\ge 2$

对于 $100\%$ 的数据，$1\leq n \leq 10^6$，$1\leq X \leq 10^{18}$，$2\leq a_i \leq 10^6$。