给定一个数组 $$$[a_1, a_2, \ldots a_n]$$$,由 $$$0$$$ 和 $$$10^9$$$ 之间的整数组成。您必须将此数组拆分为多个段(可能是一个段),以便每个元素恰好属于一个段。
设第一段为数组 $$$[a_{l_1}, a_{l_1 + 1}, \ldots, a_{r_1}]$$$,第二段为 $$$[a_{l_2}, a_{l_2+ 1}, \ldots, a_{r_2}]$$$, ...,最后一段为$$$[a_{l_k}, a_{l_k+ 1}, \ldots, a_{r_k}]$$$。由于每个元素都应该属于一个数组,因此对于从 $$$1$$$ 到 $$$k-1$$$ 的每个 $$$i$$$,$$$l_1 = 1$$$、$$$r_k = n$$$ 和 $$$r_i + 1 = l_{i+1}$$$。分割应满足以下条件: $$$f([a_{l_1}, a_{l_1 + 1}, \ldots, a_{r_1}]) \le f([a_{l_2}, a_{l_2+ 1}, \ldots, a_{r_2}]) \le \dots \le f([a_{l_k}, a_{l_k+1}, \ldots, a_{r_k}])$$$,其中 $$$f(a)$$$ 是数组 $$$a$$$ 中所有元素的按位或。
计算分割数组的方式数,并以 $$$998\,244\,353$$$ 为模打印。如果表示分割的序列 $$$[l_1, r_1, l_2, r_2, \ldots, l_k, r_k]$$$ 不同,则认为两种方式不同。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10 ^9$$$) — 给定数组的元素。
输出
打印一个整数 - 分割数组的方式数,以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
3 1 2 3
输出 #1
4
输入 #2
5 1000 1000 1000 1000 1000
输出 #2
16
输入 #3
3 3 4 6
输出 #3
3
注意
在前两个示例中,每种拆分数组的方法都是有效的。
在第三个示例中,有三种有效的方法来分割数组:
- $$$k = 3$$$; $$$l_1 = 1,r_1 = 1,l_2 = 2,r_2 = 2,l_3 = 3,r_3 = 3$$$;结果数组为 $$$[3]$$$、$$$[4]$$$、$$$[6]$$$ 和 $$$3 \le 4 \le 6$$$;
- $$$k = 2$$$; $$$l_1 = 1,r_1 = 1,l_2 = 2,r_2 = 3$$$;结果数组是 $$$[3]$$$ 和 $$$[4, 6]$$$ 和 $$$3 \le 6$$$;
- $$$k = 1$$$; $$$l_1 = 1,r_1 = 3$$$;只有一个数组:$$$[3, 4, 6]$$$。
如果将数组拆分为两个数组$$$[3, 4]$$$和$$$[6]$$$,则第一个数组的按位或为$$$7$$$,第二个数组的按位或为$$$6$$$; $$$7 > 6$$$,所以这种分割数组的方式是无效的。