#include <bits/stdc++.h>
using namespace std;
template <class T>
inline T checkmin(T &a, T b) {
  return (a < b) ? a : a = b;
}
template <class T>
inline T checkmax(T &a, T b) {
  return (a > b) ? a : a = b;
}
template <class T>
T GCD(T a, T b) {
  if (a < 0) return GCD(-a, b);
  if (b < 0) return GCD(a, -b);
  return (a == 0) ? b : GCD(b % a, a);
}
template <class T>
T LCM(T a, T b) {
  if (a < 0) return LCM(-a, b);
  if (b < 0) return LCM(a, -b);
  return (a == 0 || b == 0) ? 0 : a / GCD(a, b) * b;
}
template <class T>
inline T sqr(T X) {
  return X * X;
}
namespace Poor {
const int LogMaxiN = 60;
long long Depth[LogMaxiN];
long long Cnt[LogMaxiN][LogMaxiN];
void Pretreat() {
  for (int i = 0; i < LogMaxiN; ++i)
    for (int j = 0; j < LogMaxiN; ++j) Cnt[i][j] = 0;
  Cnt[0][0] = 1;
  Depth[0] = 1;
  for (int i = 1; i < LogMaxiN; ++i) {
    Cnt[i][0] = Cnt[i - 1][0] + 1;
    for (int j = 1; j < LogMaxiN; ++j)
      Cnt[i][j] = Cnt[i - 1][j] + Cnt[i - 1][j - 1];
    Depth[i] = Depth[i - 1] * 2 + 1;
  }
}
long long F(long long N, long long T) {
  if (N <= 0) return 0;
  if (T > N) return 0;
  int d;
  for (d = LogMaxiN - 1; Depth[d] > N; --d)
    ;
  long long Result = 0;
  for (int k = 0; k < LogMaxiN; ++k)
    if ((1LL << k) == T) Result += Cnt[d][k];
  if (N > Depth[d] && T == 1) ++Result;
  if (T % 2 == 0) Result += F(N - Depth[d] - 1, T / 2);
  return Result;
}
void Run() {
  Pretreat();
  long long N, T;
  cin >> N >> T;
  cout << F(N + 1, T) - F(1, T) << endl;
}
}  // namespace Poor
int main() {
  Poor::Run();
  return 0;
}

### Prompt

In cpp, your task is to solve the following problem:

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 ≤ 1012, 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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <class T>
inline T checkmin(T &a, T b) {
  return (a < b) ? a : a = b;
}
template <class T>
inline T checkmax(T &a, T b) {
  return (a > b) ? a : a = b;
}
template <class T>
T GCD(T a, T b) {
  if (a < 0) return GCD(-a, b);
  if (b < 0) return GCD(a, -b);
  return (a == 0) ? b : GCD(b % a, a);
}
template <class T>
T LCM(T a, T b) {
  if (a < 0) return LCM(-a, b);
  if (b < 0) return LCM(a, -b);
  return (a == 0 || b == 0) ? 0 : a / GCD(a, b) * b;
}
template <class T>
inline T sqr(T X) {
  return X * X;
}
namespace Poor {
const int LogMaxiN = 60;
long long Depth[LogMaxiN];
long long Cnt[LogMaxiN][LogMaxiN];
void Pretreat() {
  for (int i = 0; i < LogMaxiN; ++i)
    for (int j = 0; j < LogMaxiN; ++j) Cnt[i][j] = 0;
  Cnt[0][0] = 1;
  Depth[0] = 1;
  for (int i = 1; i < LogMaxiN; ++i) {
    Cnt[i][0] = Cnt[i - 1][0] + 1;
    for (int j = 1; j < LogMaxiN; ++j)
      Cnt[i][j] = Cnt[i - 1][j] + Cnt[i - 1][j - 1];
    Depth[i] = Depth[i - 1] * 2 + 1;
  }
}
long long F(long long N, long long T) {
  if (N <= 0) return 0;
  if (T > N) return 0;
  int d;
  for (d = LogMaxiN - 1; Depth[d] > N; --d)
    ;
  long long Result = 0;
  for (int k = 0; k < LogMaxiN; ++k)
    if ((1LL << k) == T) Result += Cnt[d][k];
  if (N > Depth[d] && T == 1) ++Result;
  if (T % 2 == 0) Result += F(N - Depth[d] - 1, T / 2);
  return Result;
}
void Run() {
  Pretreat();
  long long N, T;
  cin >> N >> T;
  cout << F(N + 1, T) - F(1, T) << endl;
}
}  // namespace Poor
int main() {
  Poor::Run();
  return 0;
}

```