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

### Prompt

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

```