#include <bits/stdc++.h>
using namespace std;
int n[5], p, m;
long long f[1010][10], w[5];
struct epoch {
  int x, y;
} a[3][200];
void pre() {
  ++n[0], a[0][n[0]].x = 1, a[0][n[0]].y = 2;
  ++n[1], a[1][n[1]].x = 3, a[1][n[1]].y = 3;
  ++n[2], a[2][n[2]].x = 4, a[2][n[2]].y = 4;
  ++n[1], a[1][n[1]].x = 5, a[1][n[1]].y = 6;
  ++n[2], a[2][n[2]].x = 7, a[2][n[2]].y = 8;
  ++n[0], a[0][n[0]].x = 9, a[0][n[0]].y = 12;
  ++n[1], a[1][n[1]].x = 13, a[1][n[1]].y = 14;
  ++n[2], a[2][n[2]].x = 15, a[2][n[2]].y = 18;
  ++n[0], a[0][n[0]].x = 19, a[0][n[0]].y = 26;
  ++n[1], a[1][n[1]].x = 27, a[1][n[1]].y = 38;
  ++n[2], a[2][n[2]].x = 39, a[2][n[2]].y = 39;
  ++n[0], a[0][n[0]].x = 40, a[0][n[0]].y = 56;
  ++n[2], a[2][n[2]].x = 57, a[2][n[2]].y = 57;
  ++n[1], a[1][n[1]].x = 58, a[1][n[1]].y = 80;
  ++n[2], a[2][n[2]].x = 81, a[2][n[2]].y = 84;
  ++n[0], a[0][n[0]].x = 85, a[0][n[0]].y = 119;
  ++n[2], a[2][n[2]].x = 120, a[2][n[2]].y = 120;
  ++n[1], a[1][n[1]].x = 121, a[1][n[1]].y = 173;
  ++n[2], a[2][n[2]].x = 174, a[2][n[2]].y = 178;
  ++n[0], a[0][n[0]].x = 179, a[0][n[0]].y = 254;
  ++n[2], a[2][n[2]].x = 255, a[2][n[2]].y = 259;
  ++n[1], a[1][n[1]].x = 260, a[1][n[1]].y = 362;
  ++n[2], a[2][n[2]].x = 363, a[2][n[2]].y = 381;
  ++n[0], a[0][n[0]].x = 382, a[0][n[0]].y = 536;
  ++n[2], a[2][n[2]].x = 537, a[2][n[2]].y = 543;
  ++n[1], a[1][n[1]].x = 544, a[1][n[1]].y = 779;
  ++n[2], a[2][n[2]].x = 780, a[2][n[2]].y = 804;
  ++n[0], a[0][n[0]].x = 805, a[0][n[0]].y = 1145;
  ++n[2], a[2][n[2]].x = 1146, a[2][n[2]].y = 1168;
  ++n[1], a[1][n[1]].x = 1169, a[1][n[1]].y = 1631;
  ++n[2], a[2][n[2]].x = 1632, a[2][n[2]].y = 1717;
  ++n[0], a[0][n[0]].x = 1718, a[0][n[0]].y = 2414;
  ++n[2], a[2][n[2]].x = 2415, a[2][n[2]].y = 2446;
  ++n[1], a[1][n[1]].x = 2447, a[1][n[1]].y = 3506;
  ++n[2], a[2][n[2]].x = 3507, a[2][n[2]].y = 3621;
  ++n[0], a[0][n[0]].x = 3622, a[0][n[0]].y = 5153;
  ++n[2], a[2][n[2]].x = 5154, a[2][n[2]].y = 5259;
  ++n[1], a[1][n[1]].x = 5260, a[1][n[1]].y = 7340;
  ++n[2], a[2][n[2]].x = 7341, a[2][n[2]].y = 7729;
  ++n[0], a[0][n[0]].x = 7730, a[0][n[0]].y = 10865;
  ++n[2], a[2][n[2]].x = 10866, a[2][n[2]].y = 11010;
  ++n[1], a[1][n[1]].x = 11011, a[1][n[1]].y = 15779;
  ++n[2], a[2][n[2]].x = 15780, a[2][n[2]].y = 16297;
  ++n[0], a[0][n[0]].x = 16298, a[0][n[0]].y = 23189;
  ++n[2], a[2][n[2]].x = 23190, a[2][n[2]].y = 23668;
  ++n[1], a[1][n[1]].x = 23669, a[1][n[1]].y = 33032;
  ++n[2], a[2][n[2]].x = 33033, a[2][n[2]].y = 34783;
  ++n[0], a[0][n[0]].x = 34784, a[0][n[0]].y = 48893;
  ++n[2], a[2][n[2]].x = 48894, a[2][n[2]].y = 49548;
  ++n[1], a[1][n[1]].x = 49549, a[1][n[1]].y = 71006;
  ++n[2], a[2][n[2]].x = 71007, a[2][n[2]].y = 73339;
  ++n[0], a[0][n[0]].x = 73340, a[0][n[0]].y = 104351;
  ++n[2], a[2][n[2]].x = 104352, a[2][n[2]].y = 106509;
  ++n[1], a[1][n[1]].x = 106510, a[1][n[1]].y = 148646;
  ++n[2], a[2][n[2]].x = 148647, a[2][n[2]].y = 156526;
  ++n[0], a[0][n[0]].x = 156527, a[0][n[0]].y = 220019;
  ++n[2], a[2][n[2]].x = 220020, a[2][n[2]].y = 222969;
  ++n[1], a[1][n[1]].x = 222970, a[1][n[1]].y = 319529;
  ++n[2], a[2][n[2]].x = 319530, a[2][n[2]].y = 330028;
  ++n[0], a[0][n[0]].x = 330029, a[0][n[0]].y = 469580;
  ++n[2], a[2][n[2]].x = 469581, a[2][n[2]].y = 479293;
  ++n[1], a[1][n[1]].x = 479294, a[1][n[1]].y = 668909;
  ++n[2], a[2][n[2]].x = 668910, a[2][n[2]].y = 704370;
  ++n[0], a[0][n[0]].x = 704371, a[0][n[0]].y = 990086;
  ++n[2], a[2][n[2]].x = 990087, a[2][n[2]].y = 1003363;
  ++n[1], a[1][n[1]].x = 1003364, a[1][n[1]].y = 1437881;
  ++n[2], a[2][n[2]].x = 1437882, a[2][n[2]].y = 1485129;
  ++n[0], a[0][n[0]].x = 1485130, a[0][n[0]].y = 2113112;
  ++n[2], a[2][n[2]].x = 2113113, a[2][n[2]].y = 2156821;
  ++n[1], a[1][n[1]].x = 2156822, a[1][n[1]].y = 3010091;
  ++n[2], a[2][n[2]].x = 3010092, a[2][n[2]].y = 3169668;
  ++n[0], a[0][n[0]].x = 3169669, a[0][n[0]].y = 4455389;
  ++n[2], a[2][n[2]].x = 4455390, a[2][n[2]].y = 4515136;
  ++n[1], a[1][n[1]].x = 4515137, a[1][n[1]].y = 6470465;
  ++n[2], a[2][n[2]].x = 6470466, a[2][n[2]].y = 6683083;
  ++n[0], a[0][n[0]].x = 6683084, a[0][n[0]].y = 9509006;
  ++n[2], a[2][n[2]].x = 9509007, a[2][n[2]].y = 9705697;
  ++n[1], a[1][n[1]].x = 9705698, a[1][n[1]].y = 13545410;
  ++n[2], a[2][n[2]].x = 13545411, a[2][n[2]].y = 14263509;
  ++n[0], a[0][n[0]].x = 14263510, a[0][n[0]].y = 20049251;
  ++n[2], a[2][n[2]].x = 20049252, a[2][n[2]].y = 20318115;
  ++n[1], a[1][n[1]].x = 20318116, a[1][n[1]].y = 29117093;
  ++n[2], a[2][n[2]].x = 29117094, a[2][n[2]].y = 30073876;
  ++n[0], a[0][n[0]].x = 30073877, a[0][n[0]].y = 42790529;
  ++n[2], a[2][n[2]].x = 42790530, a[2][n[2]].y = 43675639;
  ++n[1], a[1][n[1]].x = 43675640, a[1][n[1]].y = 60954347;
  ++n[2], a[2][n[2]].x = 60954348, a[2][n[2]].y = 64185793;
  ++n[0], a[0][n[0]].x = 64185794, a[0][n[0]].y = 90221630;
  ++n[2], a[2][n[2]].x = 90221631, a[2][n[2]].y = 91431520;
  ++n[1], a[1][n[1]].x = 91431521, a[1][n[1]].y = 131026919;
  ++n[2], a[2][n[2]].x = 131026920, a[2][n[2]].y = 135332445;
  ++n[0], a[0][n[0]].x = 135332446, a[0][n[0]].y = 192557381;
  ++n[2], a[2][n[2]].x = 192557382, a[2][n[2]].y = 196540378;
  ++n[1], a[1][n[1]].x = 196540379, a[1][n[1]].y = 274294562;
  ++n[2], a[2][n[2]].x = 274294563, a[2][n[2]].y = 288836071;
  ++n[0], a[0][n[0]].x = 288836072, a[0][n[0]].y = 405997337;
  ++n[2], a[2][n[2]].x = 405997338, a[2][n[2]].y = 411441843;
  ++n[1], a[1][n[1]].x = 411441844, a[1][n[1]].y = 589621136;
  ++n[2], a[2][n[2]].x = 589621137, a[2][n[2]].y = 608996005;
  ++n[0], a[0][n[0]].x = 608996006, a[0][n[0]].y = 866508215;
  ++n[2], a[2][n[2]].x = 866508216, a[2][n[2]].y = 884431704;
  ++n[1], a[1][n[1]].x = 884431705, a[1][n[1]].y = 1000000000;
}
void solve() {
  for (int i = 0; i < 3; ++i) w[i] = 0;
  for (int i = 1; i <= n[0]; ++i)
    if (a[0][i].x <= p) {
      int l = a[0][i].x, r = min(a[0][i].y, p);
      long long ret = ((long long)p * (r - l + 1)) % 1000000007 -
                      (((long long)(l + r) * (r - l + 1)) / 2) % 1000000007;
      w[0] += ((ret % 1000000007) + 1000000007) % 1000000007,
          w[0] %= 1000000007;
    }
  for (int i = 1; i <= n[1]; ++i)
    if (a[1][i].x <= p) {
      int l = a[1][i].x, r = min(a[1][i].y, p);
      long long ret = ((long long)p * (r - l + 1)) % 1000000007 -
                      (((long long)(l + r) * (r - l + 1)) / 2) % 1000000007;
      w[1] += ((ret % 1000000007) + 1000000007) % 1000000007,
          w[1] %= 1000000007;
    }
  for (int i = 1; i <= n[2]; ++i)
    if (a[2][i].x <= p) {
      int l = a[2][i].x, r = min(a[2][i].y, p);
      long long ret = ((long long)p * (r - l + 1)) % 1000000007 -
                      (((long long)(l + r) * (r - l + 1)) / 2) % 1000000007;
      w[2] += ((ret % 1000000007) + 1000000007) % 1000000007,
          w[2] %= 1000000007;
    }
  f[0][0] = 1;
  for (int i = 1; i <= m; ++i)
    for (int j = 0; j < 4; ++j)
      for (int k = 0; k < 3; ++k)
        f[i][j ^ k] =
            (f[i][j ^ k] + (f[i - 1][j] * w[k]) % 1000000007) % 1000000007;
  printf("%I64d\n", (f[m][1] + f[m][2] + f[m][3]) % 1000000007);
}
int main() {
  scanf("%d%d", &m, &p);
  pre();
  solve();
  return 0;
}

### Prompt

Your task is to create a cpp solution to the following problem:

Dima and Anya love playing different games. Now Dima has imagined a new game that he wants to play with Anya.

Dima writes n pairs of integers on a piece of paper (li, ri) (1 ≤ li < ri ≤ p). Then players take turns. On his turn the player can do the following actions:

  1. choose the number of the pair i (1 ≤ i ≤ n), such that ri - li > 2; 
  2. replace pair number i by pair <image> or by pair <image>. Notation ⌊x⌋ means rounding down to the closest integer. 



The player who can't make a move loses.

Of course, Dima wants Anya, who will move first, to win. That's why Dima should write out such n pairs of integers (li, ri) (1 ≤ li < ri ≤ p), that if both players play optimally well, the first one wins. Count the number of ways in which Dima can do it. Print the remainder after dividing the answer by number 1000000007 (109 + 7).

Two ways are considered distinct, if the ordered sequences of the written pairs are distinct.

Input

The first line contains two integers n, p (1 ≤ n ≤ 1000, 1 ≤ p ≤ 109). The numbers are separated by a single space.

Output

In a single line print the remainder after dividing the answer to the problem by number 1000000007 (109 + 7).

Examples

Input

2 2


Output

0


Input

4 4


Output

520


Input

100 1000


Output

269568947

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int n[5], p, m;
long long f[1010][10], w[5];
struct epoch {
  int x, y;
} a[3][200];
void pre() {
  ++n[0], a[0][n[0]].x = 1, a[0][n[0]].y = 2;
  ++n[1], a[1][n[1]].x = 3, a[1][n[1]].y = 3;
  ++n[2], a[2][n[2]].x = 4, a[2][n[2]].y = 4;
  ++n[1], a[1][n[1]].x = 5, a[1][n[1]].y = 6;
  ++n[2], a[2][n[2]].x = 7, a[2][n[2]].y = 8;
  ++n[0], a[0][n[0]].x = 9, a[0][n[0]].y = 12;
  ++n[1], a[1][n[1]].x = 13, a[1][n[1]].y = 14;
  ++n[2], a[2][n[2]].x = 15, a[2][n[2]].y = 18;
  ++n[0], a[0][n[0]].x = 19, a[0][n[0]].y = 26;
  ++n[1], a[1][n[1]].x = 27, a[1][n[1]].y = 38;
  ++n[2], a[2][n[2]].x = 39, a[2][n[2]].y = 39;
  ++n[0], a[0][n[0]].x = 40, a[0][n[0]].y = 56;
  ++n[2], a[2][n[2]].x = 57, a[2][n[2]].y = 57;
  ++n[1], a[1][n[1]].x = 58, a[1][n[1]].y = 80;
  ++n[2], a[2][n[2]].x = 81, a[2][n[2]].y = 84;
  ++n[0], a[0][n[0]].x = 85, a[0][n[0]].y = 119;
  ++n[2], a[2][n[2]].x = 120, a[2][n[2]].y = 120;
  ++n[1], a[1][n[1]].x = 121, a[1][n[1]].y = 173;
  ++n[2], a[2][n[2]].x = 174, a[2][n[2]].y = 178;
  ++n[0], a[0][n[0]].x = 179, a[0][n[0]].y = 254;
  ++n[2], a[2][n[2]].x = 255, a[2][n[2]].y = 259;
  ++n[1], a[1][n[1]].x = 260, a[1][n[1]].y = 362;
  ++n[2], a[2][n[2]].x = 363, a[2][n[2]].y = 381;
  ++n[0], a[0][n[0]].x = 382, a[0][n[0]].y = 536;
  ++n[2], a[2][n[2]].x = 537, a[2][n[2]].y = 543;
  ++n[1], a[1][n[1]].x = 544, a[1][n[1]].y = 779;
  ++n[2], a[2][n[2]].x = 780, a[2][n[2]].y = 804;
  ++n[0], a[0][n[0]].x = 805, a[0][n[0]].y = 1145;
  ++n[2], a[2][n[2]].x = 1146, a[2][n[2]].y = 1168;
  ++n[1], a[1][n[1]].x = 1169, a[1][n[1]].y = 1631;
  ++n[2], a[2][n[2]].x = 1632, a[2][n[2]].y = 1717;
  ++n[0], a[0][n[0]].x = 1718, a[0][n[0]].y = 2414;
  ++n[2], a[2][n[2]].x = 2415, a[2][n[2]].y = 2446;
  ++n[1], a[1][n[1]].x = 2447, a[1][n[1]].y = 3506;
  ++n[2], a[2][n[2]].x = 3507, a[2][n[2]].y = 3621;
  ++n[0], a[0][n[0]].x = 3622, a[0][n[0]].y = 5153;
  ++n[2], a[2][n[2]].x = 5154, a[2][n[2]].y = 5259;
  ++n[1], a[1][n[1]].x = 5260, a[1][n[1]].y = 7340;
  ++n[2], a[2][n[2]].x = 7341, a[2][n[2]].y = 7729;
  ++n[0], a[0][n[0]].x = 7730, a[0][n[0]].y = 10865;
  ++n[2], a[2][n[2]].x = 10866, a[2][n[2]].y = 11010;
  ++n[1], a[1][n[1]].x = 11011, a[1][n[1]].y = 15779;
  ++n[2], a[2][n[2]].x = 15780, a[2][n[2]].y = 16297;
  ++n[0], a[0][n[0]].x = 16298, a[0][n[0]].y = 23189;
  ++n[2], a[2][n[2]].x = 23190, a[2][n[2]].y = 23668;
  ++n[1], a[1][n[1]].x = 23669, a[1][n[1]].y = 33032;
  ++n[2], a[2][n[2]].x = 33033, a[2][n[2]].y = 34783;
  ++n[0], a[0][n[0]].x = 34784, a[0][n[0]].y = 48893;
  ++n[2], a[2][n[2]].x = 48894, a[2][n[2]].y = 49548;
  ++n[1], a[1][n[1]].x = 49549, a[1][n[1]].y = 71006;
  ++n[2], a[2][n[2]].x = 71007, a[2][n[2]].y = 73339;
  ++n[0], a[0][n[0]].x = 73340, a[0][n[0]].y = 104351;
  ++n[2], a[2][n[2]].x = 104352, a[2][n[2]].y = 106509;
  ++n[1], a[1][n[1]].x = 106510, a[1][n[1]].y = 148646;
  ++n[2], a[2][n[2]].x = 148647, a[2][n[2]].y = 156526;
  ++n[0], a[0][n[0]].x = 156527, a[0][n[0]].y = 220019;
  ++n[2], a[2][n[2]].x = 220020, a[2][n[2]].y = 222969;
  ++n[1], a[1][n[1]].x = 222970, a[1][n[1]].y = 319529;
  ++n[2], a[2][n[2]].x = 319530, a[2][n[2]].y = 330028;
  ++n[0], a[0][n[0]].x = 330029, a[0][n[0]].y = 469580;
  ++n[2], a[2][n[2]].x = 469581, a[2][n[2]].y = 479293;
  ++n[1], a[1][n[1]].x = 479294, a[1][n[1]].y = 668909;
  ++n[2], a[2][n[2]].x = 668910, a[2][n[2]].y = 704370;
  ++n[0], a[0][n[0]].x = 704371, a[0][n[0]].y = 990086;
  ++n[2], a[2][n[2]].x = 990087, a[2][n[2]].y = 1003363;
  ++n[1], a[1][n[1]].x = 1003364, a[1][n[1]].y = 1437881;
  ++n[2], a[2][n[2]].x = 1437882, a[2][n[2]].y = 1485129;
  ++n[0], a[0][n[0]].x = 1485130, a[0][n[0]].y = 2113112;
  ++n[2], a[2][n[2]].x = 2113113, a[2][n[2]].y = 2156821;
  ++n[1], a[1][n[1]].x = 2156822, a[1][n[1]].y = 3010091;
  ++n[2], a[2][n[2]].x = 3010092, a[2][n[2]].y = 3169668;
  ++n[0], a[0][n[0]].x = 3169669, a[0][n[0]].y = 4455389;
  ++n[2], a[2][n[2]].x = 4455390, a[2][n[2]].y = 4515136;
  ++n[1], a[1][n[1]].x = 4515137, a[1][n[1]].y = 6470465;
  ++n[2], a[2][n[2]].x = 6470466, a[2][n[2]].y = 6683083;
  ++n[0], a[0][n[0]].x = 6683084, a[0][n[0]].y = 9509006;
  ++n[2], a[2][n[2]].x = 9509007, a[2][n[2]].y = 9705697;
  ++n[1], a[1][n[1]].x = 9705698, a[1][n[1]].y = 13545410;
  ++n[2], a[2][n[2]].x = 13545411, a[2][n[2]].y = 14263509;
  ++n[0], a[0][n[0]].x = 14263510, a[0][n[0]].y = 20049251;
  ++n[2], a[2][n[2]].x = 20049252, a[2][n[2]].y = 20318115;
  ++n[1], a[1][n[1]].x = 20318116, a[1][n[1]].y = 29117093;
  ++n[2], a[2][n[2]].x = 29117094, a[2][n[2]].y = 30073876;
  ++n[0], a[0][n[0]].x = 30073877, a[0][n[0]].y = 42790529;
  ++n[2], a[2][n[2]].x = 42790530, a[2][n[2]].y = 43675639;
  ++n[1], a[1][n[1]].x = 43675640, a[1][n[1]].y = 60954347;
  ++n[2], a[2][n[2]].x = 60954348, a[2][n[2]].y = 64185793;
  ++n[0], a[0][n[0]].x = 64185794, a[0][n[0]].y = 90221630;
  ++n[2], a[2][n[2]].x = 90221631, a[2][n[2]].y = 91431520;
  ++n[1], a[1][n[1]].x = 91431521, a[1][n[1]].y = 131026919;
  ++n[2], a[2][n[2]].x = 131026920, a[2][n[2]].y = 135332445;
  ++n[0], a[0][n[0]].x = 135332446, a[0][n[0]].y = 192557381;
  ++n[2], a[2][n[2]].x = 192557382, a[2][n[2]].y = 196540378;
  ++n[1], a[1][n[1]].x = 196540379, a[1][n[1]].y = 274294562;
  ++n[2], a[2][n[2]].x = 274294563, a[2][n[2]].y = 288836071;
  ++n[0], a[0][n[0]].x = 288836072, a[0][n[0]].y = 405997337;
  ++n[2], a[2][n[2]].x = 405997338, a[2][n[2]].y = 411441843;
  ++n[1], a[1][n[1]].x = 411441844, a[1][n[1]].y = 589621136;
  ++n[2], a[2][n[2]].x = 589621137, a[2][n[2]].y = 608996005;
  ++n[0], a[0][n[0]].x = 608996006, a[0][n[0]].y = 866508215;
  ++n[2], a[2][n[2]].x = 866508216, a[2][n[2]].y = 884431704;
  ++n[1], a[1][n[1]].x = 884431705, a[1][n[1]].y = 1000000000;
}
void solve() {
  for (int i = 0; i < 3; ++i) w[i] = 0;
  for (int i = 1; i <= n[0]; ++i)
    if (a[0][i].x <= p) {
      int l = a[0][i].x, r = min(a[0][i].y, p);
      long long ret = ((long long)p * (r - l + 1)) % 1000000007 -
                      (((long long)(l + r) * (r - l + 1)) / 2) % 1000000007;
      w[0] += ((ret % 1000000007) + 1000000007) % 1000000007,
          w[0] %= 1000000007;
    }
  for (int i = 1; i <= n[1]; ++i)
    if (a[1][i].x <= p) {
      int l = a[1][i].x, r = min(a[1][i].y, p);
      long long ret = ((long long)p * (r - l + 1)) % 1000000007 -
                      (((long long)(l + r) * (r - l + 1)) / 2) % 1000000007;
      w[1] += ((ret % 1000000007) + 1000000007) % 1000000007,
          w[1] %= 1000000007;
    }
  for (int i = 1; i <= n[2]; ++i)
    if (a[2][i].x <= p) {
      int l = a[2][i].x, r = min(a[2][i].y, p);
      long long ret = ((long long)p * (r - l + 1)) % 1000000007 -
                      (((long long)(l + r) * (r - l + 1)) / 2) % 1000000007;
      w[2] += ((ret % 1000000007) + 1000000007) % 1000000007,
          w[2] %= 1000000007;
    }
  f[0][0] = 1;
  for (int i = 1; i <= m; ++i)
    for (int j = 0; j < 4; ++j)
      for (int k = 0; k < 3; ++k)
        f[i][j ^ k] =
            (f[i][j ^ k] + (f[i - 1][j] * w[k]) % 1000000007) % 1000000007;
  printf("%I64d\n", (f[m][1] + f[m][2] + f[m][3]) % 1000000007);
}
int main() {
  scanf("%d%d", &m, &p);
  pre();
  solve();
  return 0;
}

```