Максим любит заполнять матрицу специальным образом. Ниже приведен псевдокод заполнения матрицы размера (m + 1) × (m + 1):
Максим просит вас посчитать, сколько существует таких чисел m (1 ≤ m ≤ n), что сумма значений ячеек в строке с номером m + 1, полученной матрицы будет равна t.
Выражение (x xor y) обозначает применение операции побитового исключающего «ИЛИ» к числам x и y. Данная операция есть во всех современных языках программирования, например, в языке C++ и Java она обозначается символом «^», в Pascal — «xor».
Выходные данные
В единственную строку выведите целое число — ответ на задачу.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 1
|
1
|
|
2
|
3 2
|
1
|
|
3
|
3 3
|
0
|
|
4
|
1000000000000 1048576
|
118606527258
|