Maxim loves to fill in a matrix in a special manner. Here is a pseudocode of filling in a matrix of size (m + 1) × (m + 1):

[Image]

Maxim asks you to count, how many numbers m (1 ≤ m ≤ n) are there, such that the sum of values in the cells in the row number m + 1 of the resulting matrix equals t.

Expression (x xor y) means applying the operation of bitwise excluding "OR" to numbers x and y. The given operation exists in all modern programming languages. For example, in languages C++ and Java it is represented by character "^", in Pascal — by "xor".


-----Input-----

A single line contains two integers n and t (1 ≤ n, t ≤ 10^12, t ≤ n + 1).

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.


-----Output-----

In a single line print a single integer — the answer to the problem. 


-----Examples-----
Input
1 1

Output
1

Input
3 2

Output
1

Input
3 3

Output
0

Input
1000000000000 1048576

Output
118606527258

Source: codeforces | Difficulty: HARD
Tags: Dynamic programming

Mathematics

Constructive algorithms


Solutions:
(n, t) = map(int, input().split())
s = bin(n + 2)[2:]
l = len(s)
if t & t - 1:
	ans = 0
else:
	t = t.bit_length()
	f = [[0] * (l + 1) for i in range(l + 1)]
	for i in range(l + 1):
		f[i][0] = f[i][i] = 1
		for j in range(1, i):
			f[i][j] = f[i - 1][j - 1] + f[i - 1][j]
	ans = c = 0
	for i in range(l):
		if s[i] == '1':
			if t - c <= l - i - 1:
				ans += f[l - i - 1][t - c]
			c += 1
	if t == 1:
		ans -= 1
print(ans)


from math import factorial as fac
(n, t) = map(int, input().split())
if t & t - 1:
	ans = 0
else:
	ans = c = 0
	s = bin(n + 2)[2:]
	l = len(s)
	for i in range(l):
		if s[i] == '1':
			(m, k) = (l - i - 1, t.bit_length() - c)
			if 0 <= k <= m:
				ans += fac(m) // fac(k) // fac(m - k)
			c += 1
	if t == 1:
		ans -= 1
print(ans)


def comb(n, r):
	if r > n or r < 0:
		return 0
	r = min(r, n - r)
	result = 1
	for i in range(1, r + 1):
		result = result * (n + 1 - i) // i
	return result

def F(n, t):
	if t == 0:
		return 1
	elif n == 0:
		return 0
	elif n == 1:
		return int(t == 1)
	m = len(bin(n)) - 3
	return F(n - (1 << m), t - 1) + comb(m, t)
(n, t) = map(int, input().strip().split())
T = len(bin(t)) - 3
if 1 << T != t:
	print(0)
else:
	print(F(n + 1, T + 1) - int(t == 1))