1329B.md (1369B)
1 Source: https://codeforces.com/problemset/problem/1329/B 2 3 B. Dreamoon Likes Sequences 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Dreamoon likes sequences very much. So he created a problem about the sequence that you can't find in OEIS: 22 23 You are given two integers $d, m$, find the number of arrays $a$, satisfying the following constraints: 24 25 * The length of $a$ is $n$, $n \ge 1$ 26 * $1 \le a_1 \lt a_2 \lt \dots \lt a_n \le d$ 27 * Define an array $b$ of length $n$ as follows: $b_1 = a_1$, $\forall i \gt 1, b_i = b_{i - 1} \oplus a_i$, where $\oplus$ is the bitwise exclusive-or (xor). After constructing an array $b$, the constraint $b_1 \lt b_2 \lt \dots \lt b_{n - 1} \lt b_n$ should hold. 28 29 Since the number of possible arrays may be too large, you need to find the answer modulo $m$. 30 31 Input 32 33 The first line contains an integer $t$ ($1 \leq t \leq 100$) denoting the number of test cases in the input. 34 35 Each of the next $t$ lines contains two integers $d, m$ ($1 \leq d, m \leq 10^9$). 36 37 Note that $m$ is not necessary the prime! 38 39 Output 40 41 For each test case, print the number of arrays $a$, satisfying all given constrains, modulo $m$. 42 43 Example 44 45 Input 46 47 ``` 48 10 49 1 1000000000 50 2 999999999 51 3 99999998 52 4 9999997 53 5 999996 54 6 99995 55 7 9994 56 8 993 57 9 92 58 10 1 59 ``` 60 61 Output 62 63 ``` 64 1 65 3 66 5 67 11 68 17 69 23 70 29 71 59 72 89 73 0 74 ```