#include <bits/stdc++.h>
using namespace std;
const int bigp = 1000000007;
int main() {
  int x[103], y[103], z[103];
  x[1] = 1;
  y[1] = 2;
  z[1] = 0;
  x[2] = 3;
  y[2] = 3;
  z[2] = 1;
  x[3] = 4;
  y[3] = 4;
  z[3] = 2;
  x[4] = 5;
  y[4] = 6;
  z[4] = 1;
  x[5] = 7;
  y[5] = 8;
  z[5] = 2;
  x[6] = 9;
  y[6] = 12;
  z[6] = 0;
  x[7] = 13;
  y[7] = 14;
  z[7] = 1;
  x[8] = 15;
  y[8] = 18;
  z[8] = 2;
  x[9] = 19;
  y[9] = 26;
  z[9] = 0;
  x[10] = 27;
  y[10] = 38;
  z[10] = 1;
  x[11] = 39;
  y[11] = 39;
  z[11] = 2;
  x[12] = 40;
  y[12] = 56;
  z[12] = 0;
  x[13] = 57;
  y[13] = 57;
  z[13] = 2;
  x[14] = 58;
  y[14] = 80;
  z[14] = 1;
  x[15] = 81;
  y[15] = 84;
  z[15] = 2;
  x[16] = 85;
  y[16] = 119;
  z[16] = 0;
  x[17] = 120;
  y[17] = 120;
  z[17] = 2;
  x[18] = 121;
  y[18] = 173;
  z[18] = 1;
  x[19] = 174;
  y[19] = 178;
  z[19] = 2;
  x[20] = 179;
  y[20] = 254;
  z[20] = 0;
  x[21] = 255;
  y[21] = 259;
  z[21] = 2;
  x[22] = 260;
  y[22] = 362;
  z[22] = 1;
  x[23] = 363;
  y[23] = 381;
  z[23] = 2;
  x[24] = 382;
  y[24] = 536;
  z[24] = 0;
  x[25] = 537;
  y[25] = 543;
  z[25] = 2;
  x[26] = 544;
  y[26] = 779;
  z[26] = 1;
  x[27] = 780;
  y[27] = 804;
  z[27] = 2;
  x[28] = 805;
  y[28] = 1145;
  z[28] = 0;
  x[29] = 1146;
  y[29] = 1168;
  z[29] = 2;
  x[30] = 1169;
  y[30] = 1631;
  z[30] = 1;
  x[31] = 1632;
  y[31] = 1717;
  z[31] = 2;
  x[32] = 1718;
  y[32] = 2414;
  z[32] = 0;
  x[33] = 2415;
  y[33] = 2446;
  z[33] = 2;
  x[34] = 2447;
  y[34] = 3506;
  z[34] = 1;
  x[35] = 3507;
  y[35] = 3621;
  z[35] = 2;
  x[36] = 3622;
  y[36] = 5153;
  z[36] = 0;
  x[37] = 5154;
  y[37] = 5259;
  z[37] = 2;
  x[38] = 5260;
  y[38] = 7340;
  z[38] = 1;
  x[39] = 7341;
  y[39] = 7729;
  z[39] = 2;
  x[40] = 7730;
  y[40] = 10865;
  z[40] = 0;
  x[41] = 10866;
  y[41] = 11010;
  z[41] = 2;
  x[42] = 11011;
  y[42] = 15779;
  z[42] = 1;
  x[43] = 15780;
  y[43] = 16297;
  z[43] = 2;
  x[44] = 16298;
  y[44] = 23189;
  z[44] = 0;
  x[45] = 23190;
  y[45] = 23668;
  z[45] = 2;
  x[46] = 23669;
  y[46] = 33032;
  z[46] = 1;
  x[47] = 33033;
  y[47] = 34783;
  z[47] = 2;
  x[48] = 34784;
  y[48] = 48893;
  z[48] = 0;
  x[49] = 48894;
  y[49] = 49548;
  z[49] = 2;
  x[50] = 49549;
  y[50] = 71006;
  z[50] = 1;
  x[51] = 71007;
  y[51] = 73339;
  z[51] = 2;
  x[52] = 73340;
  y[52] = 104351;
  z[52] = 0;
  x[53] = 104352;
  y[53] = 106509;
  z[53] = 2;
  x[54] = 106510;
  y[54] = 148646;
  z[54] = 1;
  x[55] = 148647;
  y[55] = 156526;
  z[55] = 2;
  x[56] = 156527;
  y[56] = 220019;
  z[56] = 0;
  x[57] = 220020;
  y[57] = 222969;
  z[57] = 2;
  x[58] = 222970;
  y[58] = 319529;
  z[58] = 1;
  x[59] = 319530;
  y[59] = 330028;
  z[59] = 2;
  x[60] = 330029;
  y[60] = 469580;
  z[60] = 0;
  x[61] = 469581;
  y[61] = 479293;
  z[61] = 2;
  x[62] = 479294;
  y[62] = 668909;
  z[62] = 1;
  x[63] = 668910;
  y[63] = 704370;
  z[63] = 2;
  x[64] = 704371;
  y[64] = 990086;
  z[64] = 0;
  x[65] = 990087;
  y[65] = 1003363;
  z[65] = 2;
  x[66] = 1003364;
  y[66] = 1437881;
  z[66] = 1;
  x[67] = 1437882;
  y[67] = 1485129;
  z[67] = 2;
  x[68] = 1485130;
  y[68] = 2113112;
  z[68] = 0;
  x[69] = 2113113;
  y[69] = 2156821;
  z[69] = 2;
  x[70] = 2156822;
  y[70] = 3010091;
  z[70] = 1;
  x[71] = 3010092;
  y[71] = 3169668;
  z[71] = 2;
  x[72] = 3169669;
  y[72] = 4455389;
  z[72] = 0;
  x[73] = 4455390;
  y[73] = 4515136;
  z[73] = 2;
  x[74] = 4515137;
  y[74] = 6470465;
  z[74] = 1;
  x[75] = 6470466;
  y[75] = 6683083;
  z[75] = 2;
  x[76] = 6683084;
  y[76] = 9509006;
  z[76] = 0;
  x[77] = 9509007;
  y[77] = 9705697;
  z[77] = 2;
  x[78] = 9705698;
  y[78] = 13545410;
  z[78] = 1;
  x[79] = 13545411;
  y[79] = 14263509;
  z[79] = 2;
  x[80] = 14263510;
  y[80] = 20049251;
  z[80] = 0;
  x[81] = 20049252;
  y[81] = 20318115;
  z[81] = 2;
  x[82] = 20318116;
  y[82] = 29117093;
  z[82] = 1;
  x[83] = 29117094;
  y[83] = 30073876;
  z[83] = 2;
  x[84] = 30073877;
  y[84] = 42790529;
  z[84] = 0;
  x[85] = 42790530;
  y[85] = 43675639;
  z[85] = 2;
  x[86] = 43675640;
  y[86] = 60954347;
  z[86] = 1;
  x[87] = 60954348;
  y[87] = 64185793;
  z[87] = 2;
  x[88] = 64185794;
  y[88] = 90221630;
  z[88] = 0;
  x[89] = 90221631;
  y[89] = 91431520;
  z[89] = 2;
  x[90] = 91431521;
  y[90] = 131026919;
  z[90] = 1;
  x[91] = 131026920;
  y[91] = 135332445;
  z[91] = 2;
  x[92] = 135332446;
  y[92] = 192557381;
  z[92] = 0;
  x[93] = 192557382;
  y[93] = 196540378;
  z[93] = 2;
  x[94] = 196540379;
  y[94] = 274294562;
  z[94] = 1;
  x[95] = 274294563;
  y[95] = 288836071;
  z[95] = 2;
  x[96] = 288836072;
  y[96] = 405997337;
  z[96] = 0;
  x[97] = 405997338;
  y[97] = 411441843;
  z[97] = 2;
  x[98] = 411441844;
  y[98] = 589621136;
  z[98] = 1;
  x[99] = 589621137;
  y[99] = 608996005;
  z[99] = 2;
  x[100] = 608996006;
  y[100] = 866508215;
  z[100] = 0;
  x[101] = 866508216;
  y[101] = 884431704;
  z[101] = 2;
  x[102] = 884431705;
  y[102] = 1000000000;
  z[102] = 1;
  int n, p, o, ex, ey, tt[4], f[1005][4];
  scanf("%d %d", &n, &p);
  o = 0;
  for (int i = 1; i <= 102; i++)
    if (y[i] >= p) {
      y[i] = p;
      o = i;
      break;
    }
  memset(tt, 0, sizeof(tt));
  for (int i = 1; i <= o; i++) {
    ex = p - x[i];
    ey = p - y[i];
    tt[z[i]] = (tt[z[i]] + (long long)(ex + ey) * (ex - ey + 1) / 2) % bigp;
  }
  memset(f, 0, sizeof(f));
  f[0][0] = 1;
  for (int i = 0; i < n; i++)
    for (int j = 0; j <= 3; j++)
      for (int k = 0; k <= 2; k++)
        f[i + 1][j ^ k] = (f[i + 1][j ^ k] + (long long)f[i][j] * tt[k]) % bigp;
  printf("%d\n", ((long long)f[n][1] + f[n][2] + f[n][3]) % bigp);
  return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

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;
const int bigp = 1000000007;
int main() {
  int x[103], y[103], z[103];
  x[1] = 1;
  y[1] = 2;
  z[1] = 0;
  x[2] = 3;
  y[2] = 3;
  z[2] = 1;
  x[3] = 4;
  y[3] = 4;
  z[3] = 2;
  x[4] = 5;
  y[4] = 6;
  z[4] = 1;
  x[5] = 7;
  y[5] = 8;
  z[5] = 2;
  x[6] = 9;
  y[6] = 12;
  z[6] = 0;
  x[7] = 13;
  y[7] = 14;
  z[7] = 1;
  x[8] = 15;
  y[8] = 18;
  z[8] = 2;
  x[9] = 19;
  y[9] = 26;
  z[9] = 0;
  x[10] = 27;
  y[10] = 38;
  z[10] = 1;
  x[11] = 39;
  y[11] = 39;
  z[11] = 2;
  x[12] = 40;
  y[12] = 56;
  z[12] = 0;
  x[13] = 57;
  y[13] = 57;
  z[13] = 2;
  x[14] = 58;
  y[14] = 80;
  z[14] = 1;
  x[15] = 81;
  y[15] = 84;
  z[15] = 2;
  x[16] = 85;
  y[16] = 119;
  z[16] = 0;
  x[17] = 120;
  y[17] = 120;
  z[17] = 2;
  x[18] = 121;
  y[18] = 173;
  z[18] = 1;
  x[19] = 174;
  y[19] = 178;
  z[19] = 2;
  x[20] = 179;
  y[20] = 254;
  z[20] = 0;
  x[21] = 255;
  y[21] = 259;
  z[21] = 2;
  x[22] = 260;
  y[22] = 362;
  z[22] = 1;
  x[23] = 363;
  y[23] = 381;
  z[23] = 2;
  x[24] = 382;
  y[24] = 536;
  z[24] = 0;
  x[25] = 537;
  y[25] = 543;
  z[25] = 2;
  x[26] = 544;
  y[26] = 779;
  z[26] = 1;
  x[27] = 780;
  y[27] = 804;
  z[27] = 2;
  x[28] = 805;
  y[28] = 1145;
  z[28] = 0;
  x[29] = 1146;
  y[29] = 1168;
  z[29] = 2;
  x[30] = 1169;
  y[30] = 1631;
  z[30] = 1;
  x[31] = 1632;
  y[31] = 1717;
  z[31] = 2;
  x[32] = 1718;
  y[32] = 2414;
  z[32] = 0;
  x[33] = 2415;
  y[33] = 2446;
  z[33] = 2;
  x[34] = 2447;
  y[34] = 3506;
  z[34] = 1;
  x[35] = 3507;
  y[35] = 3621;
  z[35] = 2;
  x[36] = 3622;
  y[36] = 5153;
  z[36] = 0;
  x[37] = 5154;
  y[37] = 5259;
  z[37] = 2;
  x[38] = 5260;
  y[38] = 7340;
  z[38] = 1;
  x[39] = 7341;
  y[39] = 7729;
  z[39] = 2;
  x[40] = 7730;
  y[40] = 10865;
  z[40] = 0;
  x[41] = 10866;
  y[41] = 11010;
  z[41] = 2;
  x[42] = 11011;
  y[42] = 15779;
  z[42] = 1;
  x[43] = 15780;
  y[43] = 16297;
  z[43] = 2;
  x[44] = 16298;
  y[44] = 23189;
  z[44] = 0;
  x[45] = 23190;
  y[45] = 23668;
  z[45] = 2;
  x[46] = 23669;
  y[46] = 33032;
  z[46] = 1;
  x[47] = 33033;
  y[47] = 34783;
  z[47] = 2;
  x[48] = 34784;
  y[48] = 48893;
  z[48] = 0;
  x[49] = 48894;
  y[49] = 49548;
  z[49] = 2;
  x[50] = 49549;
  y[50] = 71006;
  z[50] = 1;
  x[51] = 71007;
  y[51] = 73339;
  z[51] = 2;
  x[52] = 73340;
  y[52] = 104351;
  z[52] = 0;
  x[53] = 104352;
  y[53] = 106509;
  z[53] = 2;
  x[54] = 106510;
  y[54] = 148646;
  z[54] = 1;
  x[55] = 148647;
  y[55] = 156526;
  z[55] = 2;
  x[56] = 156527;
  y[56] = 220019;
  z[56] = 0;
  x[57] = 220020;
  y[57] = 222969;
  z[57] = 2;
  x[58] = 222970;
  y[58] = 319529;
  z[58] = 1;
  x[59] = 319530;
  y[59] = 330028;
  z[59] = 2;
  x[60] = 330029;
  y[60] = 469580;
  z[60] = 0;
  x[61] = 469581;
  y[61] = 479293;
  z[61] = 2;
  x[62] = 479294;
  y[62] = 668909;
  z[62] = 1;
  x[63] = 668910;
  y[63] = 704370;
  z[63] = 2;
  x[64] = 704371;
  y[64] = 990086;
  z[64] = 0;
  x[65] = 990087;
  y[65] = 1003363;
  z[65] = 2;
  x[66] = 1003364;
  y[66] = 1437881;
  z[66] = 1;
  x[67] = 1437882;
  y[67] = 1485129;
  z[67] = 2;
  x[68] = 1485130;
  y[68] = 2113112;
  z[68] = 0;
  x[69] = 2113113;
  y[69] = 2156821;
  z[69] = 2;
  x[70] = 2156822;
  y[70] = 3010091;
  z[70] = 1;
  x[71] = 3010092;
  y[71] = 3169668;
  z[71] = 2;
  x[72] = 3169669;
  y[72] = 4455389;
  z[72] = 0;
  x[73] = 4455390;
  y[73] = 4515136;
  z[73] = 2;
  x[74] = 4515137;
  y[74] = 6470465;
  z[74] = 1;
  x[75] = 6470466;
  y[75] = 6683083;
  z[75] = 2;
  x[76] = 6683084;
  y[76] = 9509006;
  z[76] = 0;
  x[77] = 9509007;
  y[77] = 9705697;
  z[77] = 2;
  x[78] = 9705698;
  y[78] = 13545410;
  z[78] = 1;
  x[79] = 13545411;
  y[79] = 14263509;
  z[79] = 2;
  x[80] = 14263510;
  y[80] = 20049251;
  z[80] = 0;
  x[81] = 20049252;
  y[81] = 20318115;
  z[81] = 2;
  x[82] = 20318116;
  y[82] = 29117093;
  z[82] = 1;
  x[83] = 29117094;
  y[83] = 30073876;
  z[83] = 2;
  x[84] = 30073877;
  y[84] = 42790529;
  z[84] = 0;
  x[85] = 42790530;
  y[85] = 43675639;
  z[85] = 2;
  x[86] = 43675640;
  y[86] = 60954347;
  z[86] = 1;
  x[87] = 60954348;
  y[87] = 64185793;
  z[87] = 2;
  x[88] = 64185794;
  y[88] = 90221630;
  z[88] = 0;
  x[89] = 90221631;
  y[89] = 91431520;
  z[89] = 2;
  x[90] = 91431521;
  y[90] = 131026919;
  z[90] = 1;
  x[91] = 131026920;
  y[91] = 135332445;
  z[91] = 2;
  x[92] = 135332446;
  y[92] = 192557381;
  z[92] = 0;
  x[93] = 192557382;
  y[93] = 196540378;
  z[93] = 2;
  x[94] = 196540379;
  y[94] = 274294562;
  z[94] = 1;
  x[95] = 274294563;
  y[95] = 288836071;
  z[95] = 2;
  x[96] = 288836072;
  y[96] = 405997337;
  z[96] = 0;
  x[97] = 405997338;
  y[97] = 411441843;
  z[97] = 2;
  x[98] = 411441844;
  y[98] = 589621136;
  z[98] = 1;
  x[99] = 589621137;
  y[99] = 608996005;
  z[99] = 2;
  x[100] = 608996006;
  y[100] = 866508215;
  z[100] = 0;
  x[101] = 866508216;
  y[101] = 884431704;
  z[101] = 2;
  x[102] = 884431705;
  y[102] = 1000000000;
  z[102] = 1;
  int n, p, o, ex, ey, tt[4], f[1005][4];
  scanf("%d %d", &n, &p);
  o = 0;
  for (int i = 1; i <= 102; i++)
    if (y[i] >= p) {
      y[i] = p;
      o = i;
      break;
    }
  memset(tt, 0, sizeof(tt));
  for (int i = 1; i <= o; i++) {
    ex = p - x[i];
    ey = p - y[i];
    tt[z[i]] = (tt[z[i]] + (long long)(ex + ey) * (ex - ey + 1) / 2) % bigp;
  }
  memset(f, 0, sizeof(f));
  f[0][0] = 1;
  for (int i = 0; i < n; i++)
    for (int j = 0; j <= 3; j++)
      for (int k = 0; k <= 2; k++)
        f[i + 1][j ^ k] = (f[i + 1][j ^ k] + (long long)f[i][j] * tt[k]) % bigp;
  printf("%d\n", ((long long)f[n][1] + f[n][2] + f[n][3]) % bigp);
  return 0;
}

```