该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

任务约束

题目描述

给定 $n$ 个任务，每个任务 $i$ 的价值由数组 $a$ 给出，任务之间存在如下约束关系：

• 对于任务 $i$ $(1\leqq i\leqq n)$，若存在任务 $j$ $(1 \leqq j < i)$ 满足：$\max_{k=j}^i a_k = \bigwedge_{k=j}^i a_k$，则任务 $i$ 必须在任务 $j$ 之后执行。

求在满足所有约束条件下完成所有任务（每个任务只需执行一次）的不同方案数，结果对 $998244353$ 取模。

两个方案数不同，当且仅当至少存在某个任务在两个方案中执行顺序不一样。

$\bigwedge$ 的定义：$x\bigwedge y$ 表示 $x$ 与 $y$ 进行二进制的按位与运算，如 $1\bigwedge 5=1$。

输入格式

第一行输入一个整数 $n$ $\left (1\leqq n\leqq 10^6\right )$，表示任务数。

第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$ $\left (0\leqq a_i\leqq 10^9\right )$，表示每个任务的值。

输出格式

输出合法方案数模 $998244353$ 的结果。

输入输出样例 #1

输入 #1

3
1 2 3

输出 #1

6

合法执行任务的方案有：$[1,2,3], [1,3,2], [2,1,3], [2,3,1],[3,1,2],[3,2,1]$，共 $6$ 种方案。

输入输出样例 #2

输入 #2

6
5 5 7 7 7 5

输出 #2

60

输入输出样例 #3

输入 #3

10
1 1 1 2 3 3 4 4 4 4

输出 #3

12600

输入输出样例 #4

输入 #4

20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

输出 #4

401576539

数据范围与子任务