← 返回题目列表

Codeforces · 1329/B

B. Dreamoon 喜欢序列

中文机器翻译题面 查看原题

Dreamoon非常喜欢序列。所以他创造了一个关于序列的问题,你在 OEIS 中找不到:

给定两个整数$$$d, m$$$,求数组$$$a$$$的个数,满足以下约束:

- $$$a$$$ 的长度为 $$$n$$$, $$$n \ge 1$$$
- $$$1 \le a_1 < a_2 < \dots < a_n \le d$$$
- 定义长度为 $$$n$$$ 的数组 $$$b$$$,如下所示: $$$b_1 = a_1$$$, $$$\forall i > 1, b_i = b_{i - 1} \oplus a_i$$$,其中 $$$\oplus$$$ 是按位异或 (xor)。构造数组 $$$b$$$ 后,约束 $$$b_1 < b_2 < \dots < b_{n - 1} < b_n$$$ 应该成立。

由于可能的数组数量可能太大,您需要对 $$$m$$$ 求模答案。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) 表示输入中测试用例的数量。

接下来的 $$$t$$$ 行包含两个整数 $$$d, m$$$ ($$$1 \leq d, m \leq 10^9$$$)。

请注意,$$$m$$$ 不一定是素数!

输出

对于每个测试用例,打印满足所有给定约束的数组 $$$a$$$ 的数量,以 $$$m$$$ 为模。

示例

输入 #1

10
1 1000000000
2 999999999
3 99999998
4 9999997
5 999996
6 99995
7 9994
8 993
9 92
10 1

输出 #1

1
3
5
11
17
23
29
59
89
0