Dreamoon очень любит последовательности. Поэтому он придумал задачу про последовательность, которую нельзя найти на OEIS:
Вам дано два целых числа \(d, m\), вам нужно найти количество массивов \(a\), удовлетворяющих следующим ограничениям:
- Длина \(a\) равна \(n\), \(n \ge 1\)
- \(1 \le a_1 < a_2 < \dots < a_n \le d\)
- Рассмотрим следующий массив \(b\) длины \(n\): \(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\).
Выходные данные
Для каждого набора входных данных, выведите количество массивов \(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
3
5
11
17
23
29
59
89
0
|