#include <bits/stdc++.h>
using namespace std;
namespace IO {
const int MAXIOSIZE = 1 << 24 | 1;
unsigned char buf[MAXIOSIZE], *p1, *p2;
template <typename T>
void read(T& x) {
  x = 0;
  char ch =
      (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 24, stdin), p1 == p2)
           ? EOF
           : *p1++);
  bool flg = false;
  for (; ch < '0' || '9' < ch;
       ch = (p1 == p2 &&
                     (p2 = (p1 = buf) + fread(buf, 1, 1 << 24, stdin), p1 == p2)
                 ? EOF
                 : *p1++))
    if (ch == '-') flg |= true;
  for (; '0' <= ch && ch <= '9';
       ch = (p1 == p2 &&
                     (p2 = (p1 = buf) + fread(buf, 1, 1 << 24, stdin), p1 == p2)
                 ? EOF
                 : *p1++))
    x = x * 10 + ch - '0';
  flg ? x = -x : 0;
}
template <typename T>
void out(const T& x) {
  if (x > 9) out(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
inline void write(const T& x, const char& ed = ' ') {
  if (x < 0)
    putchar('-'), out(-x);
  else
    out(x);
  putchar(ed);
}
}  // namespace IO
const int MAXN = 40 + 10;
long long n, t;
long long num[MAXN], f[2][MAXN][MAXN];
int main() {
  IO::read(n), IO::read(t);
  if (t != (t & -t)) return puts("0"), 0;
  int s = __builtin_ctzll(t);
  ++n;
  for (int i = (40), iend = (0); i >= iend; --i) num[i] = (n >> i) & 1;
  for (int i = (0), iend = (num[40]); i <= iend; ++i)
    f[i == num[40]][40][i == 1] = 1;
  for (int i = (40), iend = (1); i >= iend; --i) {
    for (int less = (0), lessend = (1); less <= lessend; ++less) {
      for (int j = (0), jend = (40); j <= jend; ++j) {
        if (!f[less][i][j]) continue;
        for (int bit = (0), bitend = (less ? num[i - 1] : 1); bit <= bitend;
             ++bit) {
          f[less & (bit == num[i - 1])][i - 1][j + (bit == 1)] += f[less][i][j];
        }
      }
    }
  }
  IO::write(f[0][0][s + 1] + f[1][0][s + 1] - (s == 0), '\n');
  return 0;
}

### Prompt

Generate a Cpp solution to 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;
namespace IO {
const int MAXIOSIZE = 1 << 24 | 1;
unsigned char buf[MAXIOSIZE], *p1, *p2;
template <typename T>
void read(T& x) {
  x = 0;
  char ch =
      (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 24, stdin), p1 == p2)
           ? EOF
           : *p1++);
  bool flg = false;
  for (; ch < '0' || '9' < ch;
       ch = (p1 == p2 &&
                     (p2 = (p1 = buf) + fread(buf, 1, 1 << 24, stdin), p1 == p2)
                 ? EOF
                 : *p1++))
    if (ch == '-') flg |= true;
  for (; '0' <= ch && ch <= '9';
       ch = (p1 == p2 &&
                     (p2 = (p1 = buf) + fread(buf, 1, 1 << 24, stdin), p1 == p2)
                 ? EOF
                 : *p1++))
    x = x * 10 + ch - '0';
  flg ? x = -x : 0;
}
template <typename T>
void out(const T& x) {
  if (x > 9) out(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
inline void write(const T& x, const char& ed = ' ') {
  if (x < 0)
    putchar('-'), out(-x);
  else
    out(x);
  putchar(ed);
}
}  // namespace IO
const int MAXN = 40 + 10;
long long n, t;
long long num[MAXN], f[2][MAXN][MAXN];
int main() {
  IO::read(n), IO::read(t);
  if (t != (t & -t)) return puts("0"), 0;
  int s = __builtin_ctzll(t);
  ++n;
  for (int i = (40), iend = (0); i >= iend; --i) num[i] = (n >> i) & 1;
  for (int i = (0), iend = (num[40]); i <= iend; ++i)
    f[i == num[40]][40][i == 1] = 1;
  for (int i = (40), iend = (1); i >= iend; --i) {
    for (int less = (0), lessend = (1); less <= lessend; ++less) {
      for (int j = (0), jend = (40); j <= jend; ++j) {
        if (!f[less][i][j]) continue;
        for (int bit = (0), bitend = (less ? num[i - 1] : 1); bit <= bitend;
             ++bit) {
          f[less & (bit == num[i - 1])][i - 1][j + (bit == 1)] += f[less][i][j];
        }
      }
    }
  }
  IO::write(f[0][0][s + 1] + f[1][0][s + 1] - (s == 0), '\n');
  return 0;
}

```