D-异或和I_牛客练习赛153

时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 给定一个长度为 $n$ 的整数数组 $a_1, a_2, \dots, a_n$ 。
$\hspace{15pt}$ 你需要将整个数组划分成若干个非空连续段。设这些连续段的异或和依次为 $b_1, b_2, \dots, b_m$ 其中 $b_i = a_{l_i} \oplus a_{l_i+1} \oplus \cdots \oplus a_{r_i}$ 。
$\hspace{15pt}$ 为保证数组被划分为若干个非空连续段，必须有 $l_1 = 1$ ， $r_m = n$ ，且对于所有 $1 < i \leq m$ ，都有 $l_i = r_{i-1} + 1$ 。
$\hspace{15pt}$ 如果序列 $b_1, b_2, \dots, b_m$ 单调不减，即对所有 $1 \le i < m$ 都满足 $b_i \le b_{i+1}$ ，我们称这种划分是合法的。
$\hspace{15pt}$ 现在请你求出：
$\hspace{23pt}\bullet$ 在所有合法划分中，段数最多的有多少段；
$\hspace{23pt}\bullet$ 在达到最多段数的前提下，有多少种不同的合法划分方案。
$\hspace{15pt}$ 由于答案可能很大，你只需要输出方案数对给定模数 $mod$ 取模后的结果。

【名词解释】
$\hspace{15pt}$ 按位异或（ $\oplus$ ）：对两个整数的二进制表示按位进行异或运算。

输入描述:

第一行包含两个整数 ，分别表示数组长度和取模所用的模数。
第二行包含  个整数 ，表示给定数组。

输出描述:

输出一行两个整数，分别表示：
 合法划分中的最多段数；
 在达到最多段数的前提下，合法划分方案数对  取模后的结果。

示例1

输入

复制

4 998244353
1 3 2 1

输出

复制

3 2

说明

数组为，下面枚举它的所有连续划分，并判断是否合法。
划分为  段：
，异或和序列为 ，合法。
划分为  段：
，异或和序列为  即 ，不合法；
，异或和序列为  即 ，合法；
，异或和序列为  即 ，合法。
划分为  段：
，异或和序列为  即 ，合法；
，异或和序列为  即 ，合法；
，异或和序列为  即 ，不合法。
划分为  段：
，异或和序列为 ，不合法。
因此，在所有合法划分中，段数最多的有  段；在所有划分成  段的方案中，共有  种合法方案，所以答案为 。

示例2

输入

复制

4 998244353
2 1 3 1

输出

复制

2 2