| Codeforces Round 160 (Div. 1) |
|---|
| Закончено |
Максим любит заполнять матрицу специальным образом. Ниже приведен псевдокод заполнения матрицы размера (m + 1) × (m + 1):
Максим просит вас посчитать, сколько существует таких чисел m (1 ≤ m ≤ n), что сумма значений ячеек в строке с номером m + 1, полученной матрицы будет равна t.
Выражение (x xor y) обозначает применение операции побитового исключающего «ИЛИ» к числам x и y. Данная операция есть во всех современных языках программирования, например, в языке C++ и Java она обозначается символом «^», в Pascal — «xor».
В единственной строке заданы два целых числа n и t (1 ≤ n, t ≤ 1012, t ≤ n + 1).
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на C++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
В единственную строку выведите целое число — ответ на задачу.
1 1
1
3 2
1
3 3
0
1000000000000 1048576
118606527258
