时间限制： 1.0 秒

空间限制： 512 MB

题目描述

为了帮助你理解题意，我们先定义函数 $F(x)$ 表示 $x$ 在二进制表示下 $1$ 的个数。例如 $F(3) = 2$ 因为 $3$ 的二进制表示为 $11_{(2)}$；而 $F(2) = 1$ 因为 $2$ 的二进制表示为 $10_{(2)}$ 。

现在有一个 $n$ 个点的图，第 $i$ 个点的点权为 $A_i$，对于任意 $1 \le i \lt j \le n$ 有 $F(A_i \otimes A_j)$ 条从 $i$ 号点连向 $j$ 号点的不同的有向边，其中 $\otimes$ 表示二进制下按位与的操作。显然这是一个有向无环图。

请你求出：有多少条不同的从 $1$ 号点到 $n$ 号点的路径。我们认为两条路径不同，当且仅当存在至少一条边，在其中一条路径中被经过，而在另一条路径中没有被经过。由于答案可能很大，你只需要输出答案对 $991127$ 取模的结果。

注：我们认为从 $1$ 号点到 $1$ 号点（即 $n = 1$ 的特殊情况）的不同路径有 $1$ 条。

输入格式

从标准输入读入数据。

第一行一个整数 $n$，表示点的个数。

接下来一行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个点的点权 $A_i$。

输出格式

输出到标准输出。

一行一个整数表示答案对 $991127$ 取模的结果。

3
1 3 2

1

子任务

对于所有数据，保证 $1 \le n \le 2 \times 10^5,~1 \le A_i \le 10^9$。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

• 子任务 1（15 分）：$n\le 16$；
• 子任务 2（30 分）：$n\le 1000$；
• 子任务 3（10 分）：$A_i=i$；
• 子任务 4（15 分）：$A_i\le 200$；
• 子任务 5（25 分）：$A_i\le 10^5$；
• 子任务 6（5 分）：无特殊限制。