#include "FromToDivisible.cpp"

int main(int argc, char **argv)
{
  int i;
  class FromToDivisible TheClass;
  int retval;
  int N;
  int S;
  int T;
  vector <int> a;
  vector <int> b;

  if (argc != 2) { fprintf(stderr, "usage: a.out num\n"); exit(1); }

/*
  N = ;
  S = ;
  T = ;
  a = ;
  b = ;
*/


 if (atoi(argv[1]) == 0) {
    N = 11;
    S = 9;
    T = 6;
    a.push_back(3);
    a.push_back(10);
    b.push_back(5);
    b.push_back(2);
  }

 if (atoi(argv[1]) == 1) {
    N = 123456789;
    S = 18;
    T = 12;
    a.push_back(1);
    a.push_back(42);
    a.push_back(50);
    b.push_back(1);
    b.push_back(17);
    b.push_back(3);
  }

 if (atoi(argv[1]) == 2) {
    N = 60;
    S = 30;
    T = 8;
    a.push_back(16);
    a.push_back(15);
    a.push_back(12);
    b.push_back(2);
    b.push_back(20);
    b.push_back(5);
  }

 if (atoi(argv[1]) == 3) {
    N = 77;
    S = 10;
    T = 62;
    a.push_back(2);
    a.push_back(5);
    a.push_back(7);
    a.push_back(4);
    a.push_back(17);
    a.push_back(26);
    b.push_back(25);
    b.push_back(7);
    b.push_back(11);
    b.push_back(13);
    b.push_back(31);
    b.push_back(34);
  }

 if (atoi(argv[1]) == 4) {
    N = 100;
    S = 90;
    T = 40;
    a.push_back(20);
    a.push_back(30);
    a.push_back(100);
    a.push_back(99);
    a.push_back(100);
    b.push_back(10);
    b.push_back(30);
    b.push_back(100);
    b.push_back(100);
    b.push_back(99);
  }

 if (atoi(argv[1]) == 5) {
    N = 1000000000;
    S = 7000;
    T = 424212345;
    a.push_back(35000000);
    a.push_back(120000000);
    a.push_back(424212345);
    a.push_back(200000000);
    a.push_back(3500);
    a.push_back(19);
    b.push_back(15);
    b.push_back(1);
    b.push_back(7000);
    b.push_back(200000000);
    b.push_back(400000000);
    b.push_back(17);
  }

 if (atoi(argv[1]) == 6) {
    N = 2;
    S = 1;
    T = 2;
    a.push_back(2);
    b.push_back(1);
  }

 if (atoi(argv[1]) == 7) {
    N = 1000000000;
    S = 221699492;
    T = 869825265;
    a.push_back(906660545);
    a.push_back(914071332);
    a.push_back(546674226);
    a.push_back(65436974);
    a.push_back(36486149);
    a.push_back(541052406);
    a.push_back(74684889);
    a.push_back(846035224);
    a.push_back(714756927);
    a.push_back(70561759);
    a.push_back(569874292);
    a.push_back(592953677);
    a.push_back(718101400);
    a.push_back(887495882);
    a.push_back(30141044);
    a.push_back(449916121);
    a.push_back(13730386);
    a.push_back(694259170);
    a.push_back(824307829);
    a.push_back(6918727);
    a.push_back(69523629);
    a.push_back(439518988);
    a.push_back(64297856);
    a.push_back(62701634);
    a.push_back(717988662);
    a.push_back(939079403);
    a.push_back(571549186);
    a.push_back(439518988);
    a.push_back(864330042);
    a.push_back(509570973);
    a.push_back(846296315);
    a.push_back(39037046);
    a.push_back(367927383);
    a.push_back(530406650);
    a.push_back(464896663);
    a.push_back(367927383);
    a.push_back(37972588);
    a.push_back(718101400);
    a.push_back(362730712);
    a.push_back(569874292);
    a.push_back(756861067);
    a.push_back(401675068);
    a.push_back(64148788);
    a.push_back(61457693);
    a.push_back(1853091);
    a.push_back(456291950);
    a.push_back(437683803);
    a.push_back(780926758);
    a.push_back(402151583);
    a.push_back(790392502);
    a.push_back(569874292);
    a.push_back(509570973);
    a.push_back(774229806);
    a.push_back(756861067);
    a.push_back(887495882);
    a.push_back(31008221);
    a.push_back(59813555);
    a.push_back(24430873);
    a.push_back(439518988);
    a.push_back(938070375);
    a.push_back(906660545);
    a.push_back(815206147);
    a.push_back(55240555);
    a.push_back(780926758);
    a.push_back(10564143);
    a.push_back(482726064);
    a.push_back(846296315);
    a.push_back(335892162);
    a.push_back(402151583);
    a.push_back(939079403);
    a.push_back(439518988);
    a.push_back(50597680);
    a.push_back(335892162);
    a.push_back(5845109);
    a.push_back(21644);
    a.push_back(467239961);
    a.push_back(45844853);
    a.push_back(402151583);
    a.push_back(4740950);
    a.push_back(379362613);
    a.push_back(530406650);
    a.push_back(26535733);
    a.push_back(43836875);
    a.push_back(714756927);
    a.push_back(947203968);
    a.push_back(927862863);
    a.push_back(938070375);
    a.push_back(464631653);
    a.push_back(30873575);
    a.push_back(717988662);
    a.push_back(456291950);
    a.push_back(343659772);
    a.push_back(824879753);
    a.push_back(592953677);
    a.push_back(914071332);
    a.push_back(335892162);
    a.push_back(63813832);
    a.push_back(52930780);
    a.push_back(23819381);
    a.push_back(33262379);
    a.push_back(464896663);
    a.push_back(467239961);
    a.push_back(834168160);
    a.push_back(21644);
    a.push_back(864330042);
    a.push_back(846035224);
    a.push_back(401675068);
    a.push_back(718101400);
    a.push_back(34054864);
    a.push_back(741279325);
    a.push_back(694259170);
    a.push_back(774229806);
    a.push_back(356979952);
    a.push_back(568832871);
    a.push_back(569874292);
    a.push_back(44106987);
    a.push_back(50958426);
    a.push_back(546674226);
    a.push_back(996976128);
    a.push_back(482726064);
    a.push_back(31173818);
    a.push_back(790392502);
    a.push_back(362730712);
    a.push_back(15222085);
    a.push_back(571549186);
    a.push_back(44561943);
    a.push_back(824879753);
    a.push_back(815206147);
    a.push_back(32740421);
    a.push_back(996976128);
    a.push_back(530406650);
    a.push_back(456291950);
    a.push_back(464896663);
    a.push_back(12874433);
    a.push_back(780926758);
    a.push_back(6026077);
    a.push_back(482726064);
    a.push_back(914071332);
    a.push_back(568832871);
    a.push_back(694259170);
    a.push_back(449916121);
    a.push_back(899371520);
    a.push_back(996976128);
    a.push_back(714756927);
    a.push_back(33829152);
    a.push_back(834168160);
    a.push_back(887495882);
    a.push_back(938070375);
    a.push_back(906660545);
    a.push_back(66682213);
    a.push_back(718101400);
    a.push_back(815206147);
    a.push_back(35555112);
    a.push_back(69696763);
    a.push_back(437683803);
    a.push_back(993743446);
    a.push_back(996976128);
    a.push_back(32675805);
    a.push_back(8000944);
    a.push_back(55527912);
    a.push_back(50697748);
    a.push_back(20516577);
    a.push_back(927862863);
    a.push_back(367927383);
    a.push_back(10696452);
    b.push_back(64423968);
    b.push_back(9821551);
    b.push_back(938070375);
    b.push_back(780926758);
    b.push_back(571549186);
    b.push_back(569874292);
    b.push_back(927862863);
    b.push_back(864330042);
    b.push_back(65718887);
    b.push_back(824307829);
    b.push_back(33311470);
    b.push_back(864330042);
    b.push_back(18649526);
    b.push_back(335892162);
    b.push_back(887495882);
    b.push_back(694259170);
    b.push_back(824879753);
    b.push_back(78460429);
    b.push_back(914071332);
    b.push_back(717988662);
    b.push_back(694259170);
    b.push_back(82690294);
    b.push_back(717988662);
    b.push_back(568832871);
    b.push_back(18549127);
    b.push_back(509570973);
    b.push_back(335892162);
    b.push_back(31328554);
    b.push_back(467239961);
    b.push_back(68128813);
    b.push_back(343659772);
    b.push_back(780926758);
    b.push_back(993743446);
    b.push_back(482726064);
    b.push_back(717988662);
    b.push_back(2863264);
    b.push_back(467239961);
    b.push_back(21380465);
    b.push_back(482726064);
    b.push_back(13467004);
    b.push_back(846296315);
    b.push_back(939079403);
    b.push_back(993743446);
    b.push_back(906660545);
    b.push_back(509570973);
    b.push_back(546674226);
    b.push_back(26007730);
    b.push_back(4017496);
    b.push_back(439518988);
    b.push_back(53348843);
    b.push_back(28002264);
    b.push_back(774229806);
    b.push_back(906660545);
    b.push_back(53161556);
    b.push_back(834168160);
    b.push_back(815206147);
    b.push_back(509570973);
    b.push_back(756861067);
    b.push_back(464896663);
    b.push_back(824307829);
    b.push_back(63221441);
    b.push_back(846035224);
    b.push_back(887495882);
    b.push_back(24045528);
    b.push_back(401675068);
    b.push_back(43814313);
    b.push_back(32776003);
    b.push_back(362730712);
    b.push_back(12220929);
    b.push_back(906660545);
    b.push_back(717988662);
    b.push_back(846035224);
    b.push_back(81467516);
    b.push_back(439518988);
    b.push_back(41205621);
    b.push_back(14193208);
    b.push_back(714756927);
    b.push_back(464896663);
    b.push_back(509570973);
    b.push_back(437683803);
    b.push_back(68936705);
    b.push_back(541052406);
    b.push_back(362730712);
    b.push_back(34837095);
    b.push_back(899371520);
    b.push_back(541052406);
    b.push_back(914071332);
    b.push_back(456291950);
    b.push_back(717988662);
    b.push_back(815206147);
    b.push_back(824879753);
    b.push_back(947203968);
    b.push_back(938070375);
    b.push_back(996976128);
    b.push_back(887495882);
    b.push_back(2181153);
    b.push_back(694259170);
    b.push_back(541052406);
    b.push_back(482726064);
    b.push_back(927862863);
    b.push_back(57424961);
    b.push_back(464631653);
    b.push_back(571549186);
    b.push_back(379362613);
    b.push_back(456291950);
    b.push_back(22764969);
    b.push_back(71493526);
    b.push_back(541052406);
    b.push_back(464631653);
    b.push_back(449916121);
    b.push_back(790392502);
    b.push_back(26901586);
    b.push_back(568832871);
    b.push_back(6393307);
    b.push_back(401675068);
    b.push_back(993743446);
    b.push_back(482726064);
    b.push_back(824879753);
    b.push_back(32063753);
    b.push_back(780926758);
    b.push_back(592953677);
    b.push_back(714756927);
    b.push_back(530406650);
    b.push_back(717988662);
    b.push_back(19905715);
    b.push_back(571549186);
    b.push_back(83165308);
    b.push_back(592953677);
    b.push_back(464631653);
    b.push_back(846035224);
    b.push_back(39864709);
    b.push_back(53217989);
    b.push_back(815206147);
    b.push_back(509570973);
    b.push_back(356979952);
    b.push_back(947203968);
    b.push_back(46229781);
    b.push_back(36124900);
    b.push_back(756861067);
    b.push_back(7860274);
    b.push_back(714756927);
    b.push_back(258185);
    b.push_back(17300595);
    b.push_back(718101400);
    b.push_back(947203968);
    b.push_back(64948714);
    b.push_back(67993575);
    b.push_back(20986054);
    b.push_back(402151583);
    b.push_back(947203968);
    b.push_back(927862863);
    b.push_back(60265451);
    b.push_back(335892162);
    b.push_back(439518988);
    b.push_back(367927383);
    b.push_back(741279325);
    b.push_back(34066792);
    b.push_back(569874292);
    b.push_back(356979952);
    b.push_back(401675068);
    b.push_back(568832871);
    b.push_back(464631653);
    b.push_back(55443020);
    b.push_back(58252076);
    b.push_back(356979952);
 }

 if (atoi(argv[1]) == 9) {
    N = 1000000000;
    S = 932271153;
    T = 645801325;
    a.push_back(6454267);
    a.push_back(393576855);
    a.push_back(13520589);
    a.push_back(2969285);
    a.push_back(638624837);
    a.push_back(46870247);
    a.push_back(911655828);
    a.push_back(29297256);
    a.push_back(713996141);
    a.push_back(899740485);
    a.push_back(54680877);
    a.push_back(71115825);
    a.push_back(49849533);
    a.push_back(34377777);
    a.push_back(64258099);
    a.push_back(373702660);
    a.push_back(840290585);
    a.push_back(823548332);
    a.push_back(87869536);
    a.push_back(15325801);
    a.push_back(494979778);
    a.push_back(547351325);
    a.push_back(978551624);
    a.push_back(601855379);
    a.push_back(51755892);
    a.push_back(20595656);
    a.push_back(32461099);
    a.push_back(846898463);
    a.push_back(923745917);
    a.push_back(20466888);
    a.push_back(748938658);
    a.push_back(575359604);
    a.push_back(430776590);
    a.push_back(512548838);
    a.push_back(906597397);
    a.push_back(726527258);
    a.push_back(29699571);
    a.push_back(891179009);
    a.push_back(56246692);
    a.push_back(372197789);
    a.push_back(4723536);
    a.push_back(91683295);
    a.push_back(891179009);
    a.push_back(2705796);
    a.push_back(15597886);
    a.push_back(78802114);
    a.push_back(524386358);
    a.push_back(681311643);
    a.push_back(978551624);
    a.push_back(67527471);
    a.push_back(32202063);
    a.push_back(567087540);
    a.push_back(877314266);
    a.push_back(468439514);
    a.push_back(954847373);
    a.push_back(18204940);
    a.push_back(44532597);
    a.push_back(525500184);
    a.push_back(18270929);
    a.push_back(11048222);
    a.push_back(670054414);
    a.push_back(671811797);
    a.push_back(603142497);
    a.push_back(923745917);
    a.push_back(71815316);
    a.push_back(31157138);
    a.push_back(731026521);
    a.push_back(579048770);
    a.push_back(24297920);
    a.push_back(30693728);
    a.push_back(582014845);
    a.push_back(58168655);
    a.push_back(541226054);
    a.push_back(444869066);
    a.push_back(390795220);
    a.push_back(633209480);
    a.push_back(441256042);
    a.push_back(678229596);
    a.push_back(24622629);
    a.push_back(32739420);
    a.push_back(6860123);
    a.push_back(579061452);
    a.push_back(822618137);
    a.push_back(360732975);
    a.push_back(582014845);
    a.push_back(430776590);
    a.push_back(481210169);
    a.push_back(80745549);
    a.push_back(552018824);
    a.push_back(432072613);
    a.push_back(541226054);
    a.push_back(512548838);
    a.push_back(33070912);
    a.push_back(11284525);
    a.push_back(578282154);
    a.push_back(716909917);
    a.push_back(4632376);
    a.push_back(645795492);
    a.push_back(998484866);
    a.push_back(932407733);
    a.push_back(641117131);
    a.push_back(828739580);
    a.push_back(524386358);
    a.push_back(560148947);
    a.push_back(481210169);
    a.push_back(745094838);
    a.push_back(358214755);
    a.push_back(512548838);
    a.push_back(373421069);
    a.push_back(627136880);
    a.push_back(48559147);
    a.push_back(487763930);
    a.push_back(61243700);
    a.push_back(677814219);
    a.push_back(67295398);
    a.push_back(556423312);
    a.push_back(8605895);
    a.push_back(26950724);
    a.push_back(884643574);
    a.push_back(32679852);
    a.push_back(44385500);
    a.push_back(29425470);
    a.push_back(762998275);
    a.push_back(838065);
    a.push_back(368550303);
    a.push_back(401079684);
    a.push_back(75401472);
    a.push_back(459576817);
    a.push_back(390098714);
    a.push_back(400251526);
    a.push_back(70732881);
    a.push_back(567087540);
    a.push_back(726527258);
    a.push_back(614137885);
    a.push_back(37066631);
    a.push_back(49778785);
    a.push_back(622782354);
    a.push_back(55610173);
    a.push_back(910983403);
    a.push_back(79844634);
    a.push_back(494979778);
    a.push_back(525500184);
    a.push_back(76614443);
    a.push_back(53519331);
    a.push_back(998484866);
    a.push_back(899882491);
    a.push_back(444869066);
    a.push_back(608107931);
    a.push_back(896029322);
    a.push_back(59109512);
    a.push_back(960904873);
    a.push_back(34126373);
    a.push_back(491841301);
    a.push_back(528667129);
    a.push_back(60112623);
    a.push_back(7259509);
    a.push_back(801686816);
    a.push_back(55113318);
    a.push_back(370400447);
    a.push_back(845973764);
    a.push_back(748462087);
    a.push_back(687772425);
    a.push_back(54432495);
    a.push_back(63175178);
    a.push_back(17655759);
    a.push_back(462908729);
    a.push_back(854529589);
    a.push_back(348671653);
    a.push_back(547319303);
    a.push_back(35235489);
    a.push_back(392173479);
    a.push_back(79739635);
    a.push_back(36142486);
    a.push_back(48936624);
    a.push_back(45885614);
    a.push_back(713996141);
    a.push_back(621307676);
    a.push_back(600383106);
    a.push_back(51475276);
    a.push_back(559408599);
    a.push_back(896029322);
    a.push_back(553792388);
    a.push_back(553792388);
    a.push_back(559979412);
    a.push_back(557328704);
    a.push_back(670054414);
    a.push_back(978551624);
    a.push_back(514107234);
    a.push_back(846898463);
    a.push_back(801686816);
    a.push_back(373577216);
    a.push_back(535024052);
    a.push_back(622782354);
    a.push_back(745094838);
    a.push_back(1176757);
    a.push_back(617030443);
    a.push_back(373421069);
    a.push_back(16327310);
    a.push_back(8868477);
    a.push_back(42791119);
    a.push_back(603142497);
    a.push_back(52668421);
    a.push_back(896029322);
    a.push_back(40592527);
    a.push_back(547319303);
    a.push_back(541226054);
    a.push_back(840290585);
    a.push_back(553792388);
    a.push_back(726527258);
    a.push_back(17812371);
    a.push_back(2022012);
    a.push_back(549422177);
    a.push_back(732971251);
    a.push_back(420471645);
    a.push_back(53971639);
    a.push_back(378267732);
    a.push_back(3561851);
    a.push_back(35565966);
    a.push_back(44010880);
    a.push_back(696716203);
    a.push_back(860591458);
    a.push_back(641117131);
    a.push_back(390098714);
    a.push_back(547319303);
    a.push_back(22479055);
    a.push_back(665268);
    a.push_back(373702660);
    a.push_back(41913179);
    a.push_back(948296383);
    a.push_back(72147118);
    a.push_back(36199785);
    a.push_back(55647087);
    a.push_back(975304907);
    a.push_back(541226054);
    a.push_back(481210169);
    a.push_back(40482504);
    a.push_back(638306580);
    a.push_back(75386765);
    a.push_back(31593001);
    a.push_back(373421069);
    a.push_back(849426553);
    a.push_back(782685574);
    a.push_back(524386358);
    a.push_back(638306580);
    a.push_back(392173479);
    a.push_back(614137885);
    a.push_back(560745550);
    a.push_back(549422177);
    a.push_back(568761861);
    a.push_back(390098714);
    a.push_back(1336325);
    a.push_back(70493269);
    a.push_back(49544975);
    a.push_back(360732975);
    a.push_back(693178237);
    a.push_back(25321479);
    a.push_back(67645024);
    a.push_back(25761380);
    a.push_back(390795220);
    a.push_back(744522477);
    a.push_back(42755161);
    a.push_back(28513206);
    a.push_back(33068359);
    a.push_back(713996141);
    a.push_back(1965886);
    a.push_back(515302678);
    a.push_back(910983403);
    a.push_back(28302158);
    a.push_back(627136880);
    a.push_back(463808292);
    a.push_back(975304907);
    a.push_back(784837658);
    a.push_back(641225546);
    a.push_back(32671678);
    a.push_back(789346479);
    a.push_back(43029911);
    a.push_back(525500184);
    a.push_back(911655828);
    a.push_back(565908692);
    a.push_back(862791964);
    a.push_back(514107234);
    a.push_back(896029322);
    a.push_back(930240473);
    a.push_back(608107931);
    a.push_back(524386358);
    a.push_back(846117143);
    a.push_back(37994688);
    a.push_back(50785656);
    a.push_back(28628445);
    a.push_back(499571556);
    a.push_back(968427029);
    a.push_back(971392544);
    a.push_back(26019018);
    a.push_back(560328779);
    a.push_back(39739815);
    a.push_back(47509478);
    a.push_back(690371534);
    a.push_back(532290792);
    a.push_back(37923698);
    a.push_back(38115918);
    a.push_back(701875094);
    a.push_back(12666904);
    a.push_back(428636867);
    a.push_back(91608923);
    a.push_back(614137885);
    a.push_back(14873279);
    a.push_back(49723955);
    a.push_back(377800723);
    a.push_back(13708378);
    a.push_back(393576855);
    a.push_back(701875094);
    a.push_back(641117131);
    a.push_back(712687862);
    a.push_back(8275161);
    a.push_back(370400447);
    a.push_back(830838508);
    a.push_back(754193298);
    a.push_back(481210169);
    a.push_back(557328704);
    a.push_back(517728034);
    a.push_back(71142103);
    a.push_back(79510931);
    a.push_back(99461195);
    a.push_back(579048770);
    a.push_back(546727561);
    a.push_back(402760837);
    a.push_back(82661985);
    a.push_back(39968153);
    a.push_back(33129035);
    a.push_back(89838614);
    a.push_back(432072613);
    a.push_back(5491398);
    a.push_back(78972905);
    a.push_back(482935198);
    a.push_back(494979778);
    a.push_back(24770622);
    a.push_back(553677831);
    a.push_back(536312475);
    a.push_back(16723025);
    a.push_back(906597397);
    a.push_back(49622618);
    a.push_back(975304907);
    a.push_back(421662654);
    a.push_back(67125270);
    a.push_back(935658597);
    a.push_back(718221810);
    a.push_back(42829185);
    a.push_back(64702457);
    a.push_back(884643574);
    a.push_back(804857276);
    a.push_back(22127020);
    a.push_back(582014845);
    a.push_back(789346479);
    a.push_back(671811797);
    a.push_back(6864592);
    a.push_back(985009809);
    a.push_back(41361475);
    a.push_back(546727561);
    a.push_back(370400447);
    a.push_back(560148947);
    a.push_back(69994785);
    a.push_back(468439514);
    a.push_back(878935075);
    a.push_back(4705663);
    a.push_back(7917367);
    a.push_back(83383302);
    a.push_back(933680533);
    a.push_back(28454403);
    a.push_back(21618065);
    a.push_back(22927173);
    a.push_back(53330818);
    a.push_back(603142497);
    a.push_back(575359604);
    a.push_back(15290503);
    a.push_back(515302678);
    a.push_back(993718532);
    a.push_back(62898079);
    a.push_back(575359604);
    a.push_back(71883367);
    a.push_back(977430913);
    a.push_back(949860920);
    a.push_back(549422177);
    a.push_back(896029322);
    a.push_back(49046718);
    a.push_back(677814219);
    a.push_back(441256042);
    a.push_back(681311643);
    a.push_back(14764868);
    a.push_back(43353298);
    a.push_back(599414071);
    a.push_back(600383106);
    a.push_back(617030443);
    a.push_back(687772425);
    a.push_back(804857276);
    a.push_back(375624468);
    a.push_back(528303963);
    a.push_back(66512761);
    a.push_back(358214755);
    a.push_back(744522477);
    a.push_back(28239328);
    a.push_back(42301303);
    a.push_back(801686816);
    a.push_back(780665021);
    a.push_back(538031571);
    a.push_back(949860920);
    a.push_back(17384750);
    a.push_back(690371534);
    a.push_back(854529589);
    a.push_back(351826973);
    a.push_back(421662654);
    a.push_back(524386358);
    a.push_back(822618137);
    a.push_back(678229596);
    a.push_back(641117131);
    a.push_back(576565530);
    a.push_back(481210169);
    a.push_back(50774078);
    a.push_back(28418893);
    a.push_back(784837658);
    a.push_back(557328704);
    a.push_back(373577216);
    a.push_back(4161538);
    a.push_back(845973764);
    a.push_back(899882491);
    a.push_back(930747579);
    a.push_back(5022253);
    a.push_back(19917239);
    a.push_back(62414372);
    a.push_back(748462087);
    a.push_back(27068097);
    a.push_back(701875094);
    a.push_back(20776522);
    a.push_back(2815349);
    a.push_back(17106657);
    a.push_back(55042388);
    a.push_back(20671349);
    a.push_back(30691046);
    a.push_back(375624468);
    a.push_back(30597586);
    a.push_back(772412959);
    a.push_back(557328704);
    a.push_back(967439909);
    a.push_back(712687862);
    a.push_back(737722795);
    a.push_back(911655828);
    a.push_back(866273694);
    a.push_back(949860920);
    a.push_back(561641552);
    a.push_back(556423312);
    a.push_back(671811797);
    a.push_back(55545479);
    a.push_back(430776590);
    a.push_back(846898463);
    a.push_back(568761861);
    a.push_back(603142497);
    a.push_back(33688044);
    a.push_back(74869934);
    a.push_back(899740485);
    a.push_back(420471645);
    a.push_back(546727561);
    a.push_back(64318462);
    a.push_back(459576817);
    a.push_back(780665021);
    a.push_back(906597397);
    a.push_back(528667129);
    a.push_back(748938658);
    a.push_back(780665021);
    a.push_back(400317333);
    a.push_back(556423312);
    a.push_back(870797546);
    a.push_back(85311625);
    a.push_back(402760837);
    a.push_back(84751923);
    a.push_back(360732975);
    a.push_back(65788304);
    a.push_back(400317333);
    a.push_back(377800723);
    a.push_back(7271537);
    a.push_back(750533597);
    a.push_back(723144616);
    a.push_back(804326019);
    a.push_back(40733556);
    a.push_back(621307676);
    a.push_back(65604505);
    a.push_back(896029322);
    a.push_back(600383106);
    a.push_back(762643584);
    a.push_back(41020483);
    a.push_back(36555506);
    a.push_back(638624837);
    a.push_back(809591144);
    a.push_back(395878568);
    a.push_back(726527258);
    a.push_back(726527258);
    a.push_back(65086126);
    a.push_back(400317333);
    a.push_back(19145936);
    a.push_back(444869066);
    a.push_back(536164562);
    a.push_back(887810168);
    a.push_back(762643584);
    a.push_back(7029015);
    a.push_back(977430913);
    a.push_back(868448879);
    a.push_back(375624468);
    a.push_back(5053133);
    a.push_back(383758861);
    a.push_back(62150884);
    a.push_back(59776839);
    a.push_back(53744375);
    a.push_back(428636867);
    a.push_back(748938658);
    a.push_back(621307676);
    a.push_back(884643574);
    a.push_back(662381604);
    a.push_back(808011);
    a.push_back(54487872);
    a.push_back(978551624);
    a.push_back(561641552);
    a.push_back(732971251);
    a.push_back(6100179);
    a.push_back(822618137);
    a.push_back(63629827);
    a.push_back(341759805);
    a.push_back(459576817);
    a.push_back(421662654);
    a.push_back(845143);
    a.push_back(977430913);
    a.push_back(153771);
    a.push_back(546727561);
    a.push_back(48360920);
    a.push_back(561641552);
    a.push_back(823548332);
    a.push_back(663505199);
    a.push_back(932407733);
    a.push_back(681311643);
    a.push_back(601855379);
    a.push_back(731026521);
    a.push_back(75211372);
    a.push_back(968427029);
    a.push_back(58325695);
    a.push_back(822618137);
    a.push_back(52207035);
    a.push_back(535024052);
    a.push_back(373577216);
    a.push_back(39485001);
    a.push_back(804326019);
    a.push_back(13673627);
    a.push_back(441256042);
    a.push_back(846898463);
    a.push_back(39765660);
    a.push_back(14641632);
    a.push_back(560328779);
    a.push_back(13960385);
    a.push_back(718221810);
    a.push_back(69605788);
    a.push_back(972983991);
    a.push_back(621307676);
    a.push_back(370400447);
    a.push_back(559408599);
    a.push_back(608107931);
    a.push_back(47342107);
    a.push_back(383758861);
    a.push_back(732971251);
    a.push_back(559979412);
    a.push_back(599414071);
    a.push_back(899882491);
    a.push_back(373577216);
    a.push_back(19593317);
    a.push_back(801686816);
    a.push_back(961841845);
    a.push_back(41969801);
    a.push_back(44936020);
    a.push_back(26013271);
    a.push_back(666919030);
    a.push_back(748462087);
    a.push_back(82565861);
    a.push_back(428636867);
    a.push_back(830838508);
    a.push_back(949860920);
    a.push_back(373421069);
    a.push_back(963275014);
    a.push_back(608107931);
    a.push_back(663505199);
    a.push_back(58861403);
    a.push_back(373421069);
    a.push_back(733566999);
    a.push_back(528303963);
    a.push_back(552806417);
    a.push_back(975783109);
    a.push_back(88225123);
    a.push_back(508924022);
    a.push_back(733557312);
    a.push_back(41369514);
    a.push_back(15824053);
    a.push_back(499571556);
    a.push_back(809591144);
    a.push_back(341759805);
    a.push_back(22972959);
    a.push_back(29649086);
    a.push_back(641225546);
    a.push_back(843965114);
    a.push_back(784837658);
    a.push_back(378267732);
    a.push_back(846898463);
    a.push_back(372197789);
    a.push_back(608107931);
    a.push_back(547351325);
    a.push_back(39298867);
    a.push_back(690371534);
    a.push_back(978551624);
    a.push_back(748938658);
    a.push_back(83070856);
    a.push_back(645795492);
    a.push_back(400251526);
    a.push_back(481210169);
    a.push_back(49371568);
    a.push_back(737722795);
    a.push_back(693178237);
    a.push_back(76307289);
    a.push_back(681311643);
    a.push_back(830838508);
    a.push_back(64990615);
    a.push_back(421662654);
    a.push_back(681311643);
    a.push_back(645795492);
    a.push_back(978551624);
    a.push_back(45307954);
    a.push_back(677814219);
    a.push_back(887810168);
    a.push_back(70844516);
    a.push_back(868448879);
    a.push_back(528303963);
    a.push_back(1272135);
    a.push_back(402760837);
    a.push_back(552018824);
    a.push_back(750533597);
    a.push_back(32966875);
    a.push_back(4980718);
    a.push_back(19042239);
    a.push_back(923745917);
    a.push_back(46390740);
    a.push_back(843965114);
    a.push_back(12543426);
    a.push_back(514107234);
    a.push_back(739670414);
    a.push_back(600383106);
    a.push_back(993718532);
    a.push_back(515302678);
    a.push_back(754193298);
    a.push_back(627136880);
    a.push_back(561641552);
    a.push_back(26949551);
    a.push_back(933680533);
    a.push_back(733557312);
    a.push_back(754193298);
    a.push_back(25809543);
    a.push_back(463808292);
    a.push_back(745094838);
    a.push_back(968969367);
    a.push_back(45795073);
    a.push_back(846898463);
    a.push_back(993718532);
    a.push_back(878935075);
    a.push_back(963275014);
    a.push_back(932407733);
    a.push_back(390795220);
    a.push_back(35414906);
    a.push_back(927993812);
    a.push_back(963275014);
    a.push_back(47486216);
    a.push_back(43435333);
    a.push_back(599414071);
    a.push_back(18292844);
    a.push_back(754193298);
    a.push_back(549422177);
    a.push_back(967439909);
    a.push_back(553792388);
    a.push_back(540524063);
    a.push_back(63920227);
    a.push_back(515302678);
    a.push_back(701875094);
    a.push_back(782685574);
    a.push_back(528667129);
    a.push_back(633209480);
    a.push_back(741662777);
    a.push_back(998484866);
    a.push_back(860591458);
    a.push_back(967439909);
    a.push_back(804326019);
    a.push_back(754193298);
    a.push_back(46824424);
    a.push_back(884643574);
    a.push_back(9922159);
    a.push_back(617030443);
    a.push_back(12750502);
    a.push_back(28706899);
    a.push_back(351826973);
    a.push_back(57447437);
    a.push_back(5593146);
    a.push_back(58864409);
    a.push_back(61917021);
    a.push_back(528303963);
    a.push_back(726527258);
    a.push_back(508924022);
    a.push_back(772507413);
    a.push_back(809591144);
    a.push_back(46364674);
    a.push_back(76067476);
    a.push_back(556423312);
    a.push_back(372197789);
    a.push_back(50150096);
    a.push_back(931697169);
    a.push_back(718221810);
    a.push_back(737722795);
    a.push_back(762643584);
    a.push_back(45306364);
    a.push_back(39316958);
    a.push_back(463808292);
    a.push_back(4215692);
    a.push_back(690371534);
    a.push_back(549422177);
    a.push_back(57802954);
    a.push_back(508303061);
    a.push_back(74573480);
    a.push_back(752589545);
    a.push_back(63170887);
    a.push_back(393576855);
    a.push_back(10076872);
    a.push_back(23055236);
    a.push_back(701875094);
    a.push_back(8500512);
    a.push_back(26630651);
    a.push_back(441256042);
    a.push_back(582014845);
    a.push_back(21292004);
    a.push_back(823548332);
    a.push_back(622782354);
    a.push_back(400251526);
    a.push_back(559408599);
    a.push_back(32994639);
    a.push_back(52000171);
    a.push_back(36634077);
    a.push_back(368550303);
    a.push_back(931697169);
    a.push_back(866273694);
    a.push_back(537332938);
    a.push_back(633209480);
    a.push_back(36781522);
    a.push_back(421662654);
    a.push_back(3217068);
    a.push_back(737991981);
    a.push_back(713996141);
    a.push_back(603142497);
    a.push_back(579048770);
    a.push_back(561641552);
    a.push_back(582014845);
    a.push_back(508303061);
    a.push_back(822618137);
    a.push_back(78533875);
    a.push_back(896029322);
    a.push_back(6664992);
    a.push_back(40506832);
    a.push_back(525500184);
    a.push_back(737991981);
    a.push_back(745094838);
    a.push_back(854529589);
    a.push_back(662381604);
    a.push_back(621307676);
    a.push_back(15240319);
    a.push_back(40488353);
    a.push_back(696716203);
    a.push_back(528303963);
    a.push_back(45163149);
    a.push_back(993718532);
    a.push_back(8312231);
    a.push_back(638624837);
    a.push_back(972983991);
    a.push_back(633209480);
    a.push_back(960904873);
    a.push_back(532290792);
    a.push_back(42867007);
    a.push_back(42395543);
    a.push_back(390098714);
    a.push_back(971392544);
    a.push_back(910983403);
    a.push_back(935658597);
    a.push_back(68963760);
    a.push_back(712687862);
    a.push_back(546727561);
    a.push_back(32615996);
    a.push_back(48359082);
    a.push_back(772412959);
    a.push_back(49024776);
    a.push_back(61753639);
    a.push_back(15209805);
    a.push_back(20131732);
    a.push_back(402760837);
    a.push_back(687772425);
    a.push_back(641225546);
    a.push_back(662381604);
    a.push_back(862791964);
    a.push_back(392173479);
    a.push_back(41305527);
    a.push_back(557328704);
    a.push_back(561641552);
    a.push_back(535024052);
    a.push_back(866273694);
    a.push_back(931697169);
    a.push_back(43578911);
    a.push_back(19224091);
    a.push_back(567087540);
    a.push_back(891179009);
    a.push_back(772412959);
    a.push_back(39026837);
    a.push_back(487763930);
    a.push_back(998484866);
    a.push_back(60165605);
    a.push_back(83973812);
    a.push_back(638306580);
    a.push_back(930747579);
    a.push_back(628094441);
    a.push_back(24159903);
    a.push_back(948296383);
    a.push_back(22408635);
    a.push_back(891179009);
    a.push_back(2977640);
    a.push_back(540524063);
    a.push_back(567087540);
    a.push_back(525500184);
    a.push_back(822618137);
    a.push_back(557328704);
    a.push_back(732971251);
    a.push_back(641225546);
    a.push_back(70756384);
    a.push_back(535024052);
    a.push_back(16300935);
    a.push_back(51740532);
    a.push_back(537332938);
    a.push_back(713996141);
    a.push_back(59822303);
    a.push_back(508303061);
    a.push_back(10392377);
    a.push_back(64105062);
    a.push_back(963275014);
    a.push_back(47100523);
    a.push_back(830838508);
    a.push_back(402760837);
    a.push_back(16286759);
    a.push_back(784837658);
    a.push_back(840290585);
    a.push_back(927993812);
    a.push_back(560745550);
    a.push_back(395878568);
    a.push_back(395878568);
    a.push_back(614137885);
    a.push_back(25223587);
    a.push_back(395878568);
    a.push_back(822618137);
    a.push_back(390795220);
    a.push_back(8937779);
    a.push_back(491841301);
    a.push_back(16316639);
    b.push_back(741662777);
    b.push_back(633209480);
    b.push_back(608107931);
    b.push_back(532290792);
    b.push_back(61977179);
    b.push_back(536312475);
    b.push_back(878935075);
    b.push_back(578282154);
    b.push_back(843965114);
    b.push_back(638306580);
    b.push_back(372197789);
    b.push_back(993718532);
    b.push_back(748462087);
    b.push_back(933680533);
    b.push_back(608107931);
    b.push_back(561641552);
    b.push_back(878935075);
    b.push_back(7166651);
    b.push_back(963275014);
    b.push_back(748462087);
    b.push_back(553792388);
    b.push_back(906597397);
    b.push_back(42932748);
    b.push_back(737991981);
    b.push_back(576565530);
    b.push_back(732971251);
    b.push_back(866273694);
    b.push_back(25108248);
    b.push_back(5652542);
    b.push_back(599414071);
    b.push_back(14961533);
    b.push_back(63700116);
    b.push_back(575359604);
    b.push_back(383758861);
    b.push_back(3184482);
    b.push_back(375624468);
    b.push_back(927993812);
    b.push_back(65319046);
    b.push_back(840290585);
    b.push_back(841404);
    b.push_back(390098714);
    b.push_back(741662777);
    b.push_back(491841301);
    b.push_back(733557312);
    b.push_back(420471645);
    b.push_back(575359604);
    b.push_back(19359674);
    b.push_back(514107234);
    b.push_back(63675816);
    b.push_back(536164562);
    b.push_back(528667129);
    b.push_back(26466185);
    b.push_back(733557312);
    b.push_back(748462087);
    b.push_back(762998275);
    b.push_back(737991981);
    b.push_back(762998275);
    b.push_back(55596219);
    b.push_back(723144616);
    b.push_back(733566999);
    b.push_back(463808292);
    b.push_back(600383106);
    b.push_back(368550303);
    b.push_back(94361186);
    b.push_back(854529589);
    b.push_back(482935198);
    b.push_back(33683014);
    b.push_back(14844815);
    b.push_back(628094441);
    b.push_back(910983403);
    b.push_back(36176939);
    b.push_back(561641552);
    b.push_back(459576817);
    b.push_back(22191510);
    b.push_back(78610107);
    b.push_back(18836687);
    b.push_back(51210201);
    b.push_back(400251526);
    b.push_back(482935198);
    b.push_back(428636867);
    b.push_back(392173479);
    b.push_back(971392544);
    b.push_back(678229596);
    b.push_back(935658597);
    b.push_back(3520760);
    b.push_back(39479659);
    b.push_back(536312475);
    b.push_back(528667129);
    b.push_back(552806417);
    b.push_back(421662654);
    b.push_back(4359466);
    b.push_back(69874824);
    b.push_back(393576855);
    b.push_back(830838508);
    b.push_back(373702660);
    b.push_back(373421069);
    b.push_back(494979778);
    b.push_back(870797546);
    b.push_back(910983403);
    b.push_back(690371534);
    b.push_back(789346479);
    b.push_back(25832053);
    b.push_back(35907658);
    b.push_back(487763930);
    b.push_back(22733096);
    b.push_back(63678925);
    b.push_back(69241904);
    b.push_back(30362254);
    b.push_back(789346479);
    b.push_back(81141354);
    b.push_back(383758861);
    b.push_back(601855379);
    b.push_back(948296383);
    b.push_back(822618137);
    b.push_back(723144616);
    b.push_back(44777398);
    b.push_back(963275014);
    b.push_back(375624468);
    b.push_back(617030443);
    b.push_back(622782354);
    b.push_back(716909917);
    b.push_back(499571556);
    b.push_back(828739580);
    b.push_back(849426553);
    b.push_back(687772425);
    b.push_back(641117131);
    b.push_back(845973764);
    b.push_back(948296383);
    b.push_back(846898463);
    b.push_back(515302678);
    b.push_back(392173479);
    b.push_back(5490145);
    b.push_back(54894785);
    b.push_back(28062263);
    b.push_back(373702660);
    b.push_back(645795492);
    b.push_back(906597397);
    b.push_back(750533597);
    b.push_back(372197789);
    b.push_back(375624468);
    b.push_back(46637542);
    b.push_back(868448879);
    b.push_back(677814219);
    b.push_back(560328779);
    b.push_back(44813482);
    b.push_back(47966585);
    b.push_back(39832794);
    b.push_back(54118598);
    b.push_back(1779477);
    b.push_back(541226054);
    b.push_back(693178237);
    b.push_back(782685574);
    b.push_back(968969367);
    b.push_back(36247215);
    b.push_back(741662777);
    b.push_back(896029322);
    b.push_back(468439514);
    b.push_back(393576855);
    b.push_back(79509339);
    b.push_back(60728897);
    b.push_back(540524063);
    b.push_back(846898463);
    b.push_back(557328704);
    b.push_back(935658597);
    b.push_back(985009809);
    b.push_back(845973764);
    b.push_back(772412959);
    b.push_back(739670414);
    b.push_back(663505199);
    b.push_back(741662777);
    b.push_back(390795220);
    b.push_back(432072613);
    b.push_back(849426553);
    b.push_back(400251526);
    b.push_back(462908729);
    b.push_back(33895292);
    b.push_back(29763901);
    b.push_back(17171146);
    b.push_back(975783109);
    b.push_back(16734315);
    b.push_back(33838586);
    b.push_back(35274577);
    b.push_back(28326467);
    b.push_back(508924022);
    b.push_back(43886531);
    b.push_back(931697169);
    b.push_back(59721088);
    b.push_back(401079684);
    b.push_back(532290792);
    b.push_back(79197575);
    b.push_back(560328779);
    b.push_back(998484866);
    b.push_back(18903607);
    b.push_back(21096570);
    b.push_back(560328779);
    b.push_back(13106174);
    b.push_back(444869066);
    b.push_back(601855379);
    b.push_back(608107931);
    b.push_back(846898463);
    b.push_back(42780065);
    b.push_back(737722795);
    b.push_back(978551624);
    b.push_back(532290792);
    b.push_back(923745917);
    b.push_back(53476542);
    b.push_back(82269823);
    b.push_back(782685574);
    b.push_back(7871598);
    b.push_back(393576855);
    b.push_back(463808292);
    b.push_back(666919030);
    b.push_back(10969882);
    b.push_back(552018824);
    b.push_back(420471645);
    b.push_back(750533597);
    b.push_back(927993812);
    b.push_back(641117131);
    b.push_back(377800723);
    b.push_back(745094838);
    b.push_back(930240473);
    b.push_back(53013287);
    b.push_back(31096512);
    b.push_back(10004066);
    b.push_back(525500184);
    b.push_back(557328704);
    b.push_back(772412959);
    b.push_back(528303963);
    b.push_back(977430913);
    b.push_back(822618137);
    b.push_back(341759805);
    b.push_back(441256042);
    b.push_back(358214755);
    b.push_back(7310599);
    b.push_back(46581826);
    b.push_back(547319303);
    b.push_back(80770337);
    b.push_back(877314266);
    b.push_back(748462087);
    b.push_back(41667770);
    b.push_back(666919030);
    b.push_back(975304907);
    b.push_back(19574513);
    b.push_back(696716203);
    b.push_back(737722795);
    b.push_back(804857276);
    b.push_back(432072613);
    b.push_back(62225173);
    b.push_back(960904873);
    b.push_back(14146914);
    b.push_back(862791964);
    b.push_back(923745917);
    b.push_back(748938658);
    b.push_back(681311643);
    b.push_back(968427029);
    b.push_back(512548838);
    b.push_back(546727561);
    b.push_back(860591458);
    b.push_back(723144616);
    b.push_back(627136880);
    b.push_back(739670414);
    b.push_back(576565530);
    b.push_back(930747579);
    b.push_back(395878568);
    b.push_back(780665021);
    b.push_back(48156596);
    b.push_back(804326019);
    b.push_back(383758861);
    b.push_back(43575054);
    b.push_back(517728034);
    b.push_back(86981341);
    b.push_back(48910223);
    b.push_back(377800723);
    b.push_back(884643574);
    b.push_back(18167171);
    b.push_back(560328779);
    b.push_back(39637839);
    b.push_back(395878568);
    b.push_back(494979778);
    b.push_back(39734616);
    b.push_back(56662445);
    b.push_back(608107931);
    b.push_back(809591144);
    b.push_back(383758861);
    b.push_back(44547842);
    b.push_back(525500184);
    b.push_back(528303963);
    b.push_back(633209480);
    b.push_back(804857276);
    b.push_back(46103761);
    b.push_back(565908692);
    b.push_back(568761861);
    b.push_back(977430913);
    b.push_back(541226054);
    b.push_back(561641552);
    b.push_back(552806417);
    b.push_back(58209862);
    b.push_back(341759805);
    b.push_back(862791964);
    b.push_back(370400447);
    b.push_back(43119461);
    b.push_back(621307676);
    b.push_back(33351270);
    b.push_back(444869066);
    b.push_back(78953405);
    b.push_back(754193298);
    b.push_back(846117143);
    b.push_back(30099117);
    b.push_back(538031571);
    b.push_back(508924022);
    b.push_back(2907282);
    b.push_back(716909917);
    b.push_back(55930110);
    b.push_back(762643584);
    b.push_back(556423312);
    b.push_back(25529486);
    b.push_back(670054414);
    b.push_back(830838508);
    b.push_back(53036835);
    b.push_back(931697169);
    b.push_back(854529589);
    b.push_back(552806417);
    b.push_back(899882491);
    b.push_back(975783109);
    b.push_back(62420368);
    b.push_back(71452395);
    b.push_back(752589545);
    b.push_back(840290585);
    b.push_back(930747579);
    b.push_back(878935075);
    b.push_back(17156051);
    b.push_back(383758861);
    b.push_back(899740485);
    b.push_back(547319303);
    b.push_back(1030928);
    b.push_back(351826973);
    b.push_back(884643574);
    b.push_back(899882491);
    b.push_back(370400447);
    b.push_back(402760837);
    b.push_back(878935075);
    b.push_back(49164073);
    b.push_back(3697613);
    b.push_back(723144616);
    b.push_back(741662777);
    b.push_back(378267732);
    b.push_back(804857276);
    b.push_back(400251526);
    b.push_back(62532445);
    b.push_back(53252592);
    b.push_back(508303061);
    b.push_back(967439909);
    b.push_back(444869066);
    b.push_back(762643584);
    b.push_back(400251526);
    b.push_back(546727561);
    b.push_back(845973764);
    b.push_back(42415915);
    b.push_back(21187844);
    b.push_back(36496340);
    b.push_back(641117131);
    b.push_back(662381604);
    b.push_back(360732975);
    b.push_back(906597397);
    b.push_back(390795220);
    b.push_back(899882491);
    b.push_back(35835335);
    b.push_back(726527258);
    b.push_back(731026521);
    b.push_back(491841301);
    b.push_back(628094441);
    b.push_back(8010194);
    b.push_back(822618137);
    b.push_back(993718532);
    b.push_back(35897813);
    b.push_back(10622331);
    b.push_back(395878568);
    b.push_back(690371534);
    b.push_back(968969367);
    b.push_back(10358352);
    b.push_back(25922166);
    b.push_back(849426553);
    b.push_back(25918540);
    b.push_back(701875094);
    b.push_back(35026117);
    b.push_back(15408588);
    b.push_back(40213263);
    b.push_back(963275014);
    b.push_back(737722795);
    b.push_back(14834127);
    b.push_back(46555259);
    b.push_back(2443467);
    b.push_back(390098714);
    b.push_back(870797546);
    b.push_back(7323976);
    b.push_back(50013958);
    b.push_back(748462087);
    b.push_back(428636867);
    b.push_back(36261845);
    b.push_back(546727561);
    b.push_back(843965114);
    b.push_back(11719858);
    b.push_back(954847373);
    b.push_back(375624468);
    b.push_back(481210169);
    b.push_back(428636867);
    b.push_back(15275836);
    b.push_back(19159818);
    b.push_back(575359604);
    b.push_back(71402950);
    b.push_back(578282154);
    b.push_back(400251526);
    b.push_back(2714186);
    b.push_back(5834674);
    b.push_back(603142497);
    b.push_back(50769009);
    b.push_back(373421069);
    b.push_back(541226054);
    b.push_back(567087540);
    b.push_back(46206372);
    b.push_back(15110708);
    b.push_back(927993812);
    b.push_back(400317333);
    b.push_back(549422177);
    b.push_back(9633440);
    b.push_back(373577216);
    b.push_back(567087540);
    b.push_back(487763930);
    b.push_back(46137089);
    b.push_back(772507413);
    b.push_back(560328779);
    b.push_back(582014845);
    b.push_back(701875094);
    b.push_back(985009809);
    b.push_back(549422177);
    b.push_back(930240473);
    b.push_back(351826973);
    b.push_back(482935198);
    b.push_back(567087540);
    b.push_back(70005122);
    b.push_back(393576855);
    b.push_back(31821375);
    b.push_back(28399845);
    b.push_back(31890639);
    b.push_back(40946376);
    b.push_back(52263824);
    b.push_back(38792845);
    b.push_back(4657529);
    b.push_back(27470256);
    b.push_back(641225546);
    b.push_back(948296383);
    b.push_back(4983912);
    b.push_back(16391506);
    b.push_back(74898161);
    b.push_back(20052981);
    b.push_back(723144616);
    b.push_back(546727561);
    b.push_back(745094838);
    b.push_back(85410240);
    b.push_back(19015577);
    b.push_back(599414071);
    b.push_back(1751517);
    b.push_back(11415704);
    b.push_back(43432532);
    b.push_back(36392470);
    b.push_back(18551379);
    b.push_back(28167261);
    b.push_back(899740485);
    b.push_back(701875094);
    b.push_back(927993812);
    b.push_back(372197789);
    b.push_back(41298333);
    b.push_back(718221810);
    b.push_back(6704010);
    b.push_back(804857276);
    b.push_back(77924536);
    b.push_back(860591458);
    b.push_back(860591458);
    b.push_back(560745550);
    b.push_back(348671653);
    b.push_back(762643584);
    b.push_back(638624837);
    b.push_back(10007671);
    b.push_back(560148947);
    b.push_back(67144596);
    b.push_back(44773760);
    b.push_back(24931081);
    b.push_back(899882491);
    b.push_back(494979778);
    b.push_back(41359050);
    b.push_back(961841845);
    b.push_back(490273);
    b.push_back(538031571);
    b.push_back(93340831);
    b.push_back(375624468);
    b.push_back(59186408);
    b.push_back(560328779);
    b.push_back(524386358);
    b.push_back(670054414);
    b.push_back(967439909);
    b.push_back(86318018);
    b.push_back(681311643);
    b.push_back(6858348);
    b.push_back(499571556);
    b.push_back(12942417);
    b.push_back(822618137);
    b.push_back(9444834);
    b.push_back(372197789);
    b.push_back(860591458);
    b.push_back(693178237);
    b.push_back(66825525);
    b.push_back(10808270);
    b.push_back(420471645);
    b.push_back(30493192);
    b.push_back(40422019);
    b.push_back(701875094);
    b.push_back(739670414);
    b.push_back(608107931);
    b.push_back(772412959);
    b.push_back(393576855);
    b.push_back(600383106);
    b.push_back(61344806);
    b.push_back(576565530);
    b.push_back(744522477);
    b.push_back(5705925);
    b.push_back(877314266);
    b.push_back(421662654);
    b.push_back(933680533);
    b.push_back(967439909);
    b.push_back(731026521);
    b.push_back(420471645);
    b.push_back(44206960);
    b.push_back(90594955);
    b.push_back(972983991);
    b.push_back(430776590);
    b.push_back(72249765);
    b.push_back(40436799);
    b.push_back(732971251);
    b.push_back(617030443);
    b.push_back(17793307);
    b.push_back(628094441);
    b.push_back(42366917);
    b.push_back(373421069);
    b.push_back(910983403);
    b.push_back(459576817);
    b.push_back(784837658);
    b.push_back(41897662);
    b.push_back(663505199);
    b.push_back(985009809);
    b.push_back(25584607);
    b.push_back(599414071);
    b.push_back(846898463);
    b.push_back(18810565);
    b.push_back(726527258);
    b.push_back(54450356);
    b.push_back(712687862);
    b.push_back(971392544);
    b.push_back(39771778);
    b.push_back(3394203);
    b.push_back(1633294);
    b.push_back(33539570);
    b.push_back(732971251);
    b.push_back(370400447);
    b.push_back(73819);
    b.push_back(393576855);
    b.push_back(30848070);
    b.push_back(18437430);
    b.push_back(541226054);
    b.push_back(961841845);
    b.push_back(85691000);
    b.push_back(846117143);
    b.push_back(745094838);
    b.push_back(370400447);
    b.push_back(933680533);
    b.push_back(621307676);
    b.push_back(662381604);
    b.push_back(726527258);
    b.push_back(733566999);
    b.push_back(6187651);
    b.push_back(26951124);
    b.push_back(40767383);
    b.push_back(744522477);
    b.push_back(63964644);
    b.push_back(579061452);
    b.push_back(536312475);
    b.push_back(524386358);
    b.push_back(891179009);
    b.push_back(3336518);
    b.push_back(754193298);
    b.push_back(712687862);
    b.push_back(737722795);
    b.push_back(6053488);
    b.push_back(528667129);
    b.push_back(358214755);
    b.push_back(887810168);
    b.push_back(576565530);
    b.push_back(55372457);
    b.push_back(22058180);
    b.push_back(884643574);
    b.push_back(662381604);
    b.push_back(2520135);
    b.push_back(41250828);
    b.push_back(35385886);
    b.push_back(8906507);
    b.push_back(23265592);
    b.push_back(752589545);
    b.push_back(512548838);
    b.push_back(622782354);
    b.push_back(358214755);
    b.push_back(677814219);
    b.push_back(383758861);
    b.push_back(351826973);
    b.push_back(830838508);
    b.push_back(23774568);
    b.push_back(713996141);
    b.push_back(38674860);
    b.push_back(690371534);
    b.push_back(30778158);
    b.push_back(67086731);
    b.push_back(641225546);
    b.push_back(1975887);
    b.push_back(45138303);
    b.push_back(373421069);
    b.push_back(3864502);
    b.push_back(401079684);
    b.push_back(614137885);
    b.push_back(8087863);
    b.push_back(975304907);
    b.push_back(7109756);
    b.push_back(582014845);
    b.push_back(762998275);
    b.push_back(576565530);
    b.push_back(34605194);
    b.push_back(400251526);
    b.push_back(2169265);
    b.push_back(70542140);
    b.push_back(62689002);
    b.push_back(508924022);
    b.push_back(896029322);
    b.push_back(712687862);
    b.push_back(663505199);
    b.push_back(358214755);
    b.push_back(911655828);
    b.push_back(744522477);
    b.push_back(5840109);
    b.push_back(559408599);
    b.push_back(762643584);
    b.push_back(33550819);
    b.push_back(42517955);
    b.push_back(28532836);
    b.push_back(784837658);
    b.push_back(2022778);
    b.push_back(846898463);
    b.push_back(462908729);
    b.push_back(537332938);
    b.push_back(536164562);
    b.push_back(733557312);
    b.push_back(45017353);
    b.push_back(12693922);
    b.push_back(528303963);
    b.push_back(772412959);
    b.push_back(55770643);
    b.push_back(720187);
    b.push_back(4472248);
    b.push_back(627136880);
    b.push_back(65374271);
    b.push_back(57684294);
    b.push_back(579061452);
    b.push_back(535024052);
    b.push_back(341759805);
    b.push_back(975783109);
    b.push_back(372197789);
    b.push_back(638624837);
    b.push_back(515302678);
    b.push_back(463808292);
    b.push_back(24256555);
    b.push_back(553677831);
    b.push_back(26191536);
    b.push_back(24109562);
    b.push_back(383758861);
    b.push_back(930747579);
    b.push_back(7388689);
    b.push_back(58564689);
    b.push_back(537332938);
    b.push_back(60491788);
    b.push_back(681311643);
    b.push_back(5396243);
    b.push_back(35202800);
    b.push_back(54490535);
    b.push_back(671811797);
    b.push_back(66798552);
    b.push_back(911655828);
    b.push_back(70419750);
    b.push_back(375624468);
    b.push_back(726527258);
    b.push_back(557328704);
    b.push_back(508924022);
    b.push_back(932407733);
    b.push_back(677814219);
    b.push_back(383758861);
    b.push_back(540524063);
    b.push_back(780665021);
    b.push_back(801686816);
    b.push_back(40552773);
    b.push_back(633209480);
    b.push_back(628094441);
    b.push_back(8943247);
    b.push_back(546727561);
    b.push_back(535024052);
    b.push_back(67642029);
    b.push_back(67641733);
    b.push_back(390098714);
    b.push_back(579048770);
    b.push_back(10019640);
    b.push_back(862791964);
    b.push_back(641225546);
    b.push_back(578282154);
    b.push_back(641225546);
    b.push_back(59344108);
    b.push_back(693178237);
    b.push_back(4138114);
    b.push_back(28945433);
    b.push_back(556423312);
    b.push_back(49040896);
    b.push_back(737991981);
    b.push_back(804326019);
    b.push_back(559979412);
    b.push_back(56580855);
    b.push_back(608107931);
    b.push_back(754193298);
    b.push_back(373577216);
    b.push_back(525500184);
    b.push_back(977430913);
    b.push_back(970607);
    b.push_back(553677831);
    b.push_back(578282154);
    b.push_back(896029322);
    b.push_back(84380677);
    b.push_back(60025245);
    b.push_back(949860920);
    b.push_back(575359604);
    b.push_back(716909917);
    b.push_back(536312475);
    b.push_back(6050186);
    b.push_back(975783109);
    b.push_back(877314266);
    b.push_back(887810168);
    b.push_back(645795492);
    b.push_back(430776590);
    b.push_back(866273694);
    b.push_back(745094838);
    b.push_back(547351325);
    b.push_back(44784096);
    b.push_back(58748979);
    b.push_back(33344005);
    b.push_back(854529589);
    b.push_back(45358517);
    b.push_back(351826973);
    b.push_back(27718864);
    b.push_back(552806417);
    b.push_back(512548838);
    b.push_back(748938658);
    b.push_back(713996141);
    b.push_back(42293061);
    b.push_back(16919356);
    b.push_back(993718532);
    b.push_back(73360580);
    b.push_back(5586481);
    b.push_back(4397897);
    b.push_back(911655828);
    b.push_back(508303061);
    b.push_back(2406440);
    b.push_back(468439514);
    b.push_back(549422177);
    b.push_back(508303061);
    b.push_back(600383106);
    b.push_back(441256042);
    b.push_back(579061452);
    b.push_back(614137885);
    b.push_back(72593019);
    b.push_back(963275014);
    b.push_back(400251526);
    b.push_back(972983991);
    b.push_back(38457406);
    b.push_back(40940855);
    b.push_back(25717062);
    b.push_back(14727460);
    b.push_back(351826973);
    b.push_back(560148947);
    b.push_back(40028654);
    b.push_back(663505199);
    b.push_back(360732975);
    b.push_back(599414071);
    b.push_back(822618137);
    b.push_back(968969367);
    b.push_back(370400447);
    b.push_back(930747579);
    b.push_back(33480849);
    b.push_back(38942674);
    b.push_back(70637788);
    b.push_back(823548332);
    b.push_back(390795220);
    b.push_back(66055157);
    b.push_back(830838508);
    b.push_back(559979412);
    b.push_back(3409646);
    b.push_back(75756723);
    b.push_back(59633450);
    b.push_back(70086934);
    b.push_back(368550303);
    b.push_back(528667129);
    b.push_back(82253187);
    b.push_back(32970664);
    b.push_back(44823038);
    b.push_back(891179009);
    b.push_back(43761875);
    b.push_back(34685057);
    b.push_back(351826973);
    b.push_back(628094441);
    b.push_back(14842664);
    b.push_back(713996141);
    b.push_back(780665021);
    b.push_back(804857276);
    b.push_back(933680533);
    b.push_back(843965114);
    b.push_back(968969367);
    b.push_back(752589545);
    b.push_back(662381604);
    b.push_back(392173479);
    b.push_back(28567829);
    b.push_back(90736657);
    b.push_back(48117569);
    b.push_back(557328704);
    b.push_back(930240473);
    b.push_back(780665021);
    b.push_back(14682817);
    b.push_back(459576817);
    b.push_back(638624837);
    b.push_back(45732936);
    b.push_back(18814319);
    b.push_back(341759805);
    b.push_back(748938658);
    b.push_back(528667129);
    b.push_back(517728034);
    b.push_back(27312361);
    b.push_back(975304907);
    b.push_back(536312475);
    b.push_back(772507413);
    b.push_back(896029322);
    b.push_back(71206340);
    b.push_back(16541617);
    b.push_back(50985587);
    b.push_back(57028330);
    b.push_back(27373686);
    b.push_back(30913287);
    b.push_back(82373588);
    b.push_back(373577216);
    b.push_back(840290585);
    b.push_back(45729971);
    b.push_back(739670414);
    b.push_back(963275014);
    b.push_back(27506571);
    b.push_back(911655828);
  }

 if (atoi(argv[1]) == 19) {
    N = 100000000;
    S = 92315852;
    T = 93780753;
    a.push_back(99200349);
    a.push_back(62646077);
    a.push_back(43559845);
    a.push_back(52401761);
    a.push_back(97662651);
    a.push_back(46917032);
    a.push_back(77549825);
    a.push_back(1895370);
    a.push_back(83036137);
    a.push_back(95136974);
    a.push_back(64951365);
    a.push_back(70792567);
    a.push_back(40705818);
    a.push_back(34225686);
    a.push_back(72140401);
    a.push_back(37791454);
    a.push_back(35317490);
    a.push_back(83611418);
    a.push_back(35566564);
    a.push_back(51045456);
    a.push_back(58667405);
    a.push_back(49400882);
    a.push_back(36499673);
    a.push_back(62253863);
    a.push_back(88963645);
    a.push_back(63766349);
    a.push_back(91614958);
    a.push_back(56599734);
    a.push_back(88432110);
    a.push_back(69634353);
    a.push_back(66671476);
    a.push_back(76880320);
    a.push_back(57488493);
    a.push_back(54117396);
    a.push_back(98474574);
    a.push_back(67005790);
    a.push_back(74545376);
    a.push_back(43968964);
    a.push_back(59085025);
    a.push_back(69684256);
    a.push_back(78656139);
    a.push_back(80925392);
    a.push_back(65221849);
    a.push_back(89566971);
    a.push_back(67857444);
    a.push_back(85027514);
    a.push_back(82203044);
    a.push_back(46922251);
    a.push_back(70649162);
    a.push_back(1556260);
    a.push_back(93965610);
    a.push_back(38429734);
    a.push_back(40919789);
    a.push_back(40072500);
    a.push_back(95804869);
    a.push_back(59515346);
    a.push_back(98288946);
    a.push_back(55912215);
    a.push_back(39102507);
    a.push_back(86366944);
    a.push_back(89859115);
    a.push_back(71284477);
    a.push_back(72714394);
    a.push_back(80720190);
    a.push_back(48595629);
    a.push_back(51013089);
    a.push_back(98345170);
    a.push_back(99019616);
    a.push_back(41855137);
    a.push_back(59696359);
    a.push_back(92315852);
    a.push_back(78485431);
    a.push_back(87783379);
    a.push_back(50868655);
    a.push_back(89361880);
    a.push_back(97528379);
    a.push_back(73084750);
    a.push_back(35484038);
    a.push_back(81736121);
    a.push_back(34292960);
    a.push_back(70332336);
    a.push_back(66983362);
    a.push_back(69145396);
    a.push_back(43968964);
    a.push_back(44204114);
    a.push_back(93965610);
    a.push_back(85567856);
    a.push_back(53310394);
    a.push_back(81056734);
    a.push_back(50379946);
    a.push_back(38437905);
    a.push_back(88293733);
    a.push_back(56427995);
    a.push_back(68281549);
    a.push_back(53310394);
    a.push_back(72826360);
    a.push_back(94439937);
    a.push_back(58100930);
    a.push_back(96703184);
    a.push_back(58100930);
    a.push_back(46766908);
    a.push_back(67893661);
    a.push_back(92880627);
    a.push_back(54597733);
    a.push_back(46210307);
    a.push_back(94845200);
    a.push_back(92478458);
    a.push_back(34124878);
    a.push_back(59784243);
    a.push_back(74507030);
    a.push_back(81475759);
    a.push_back(47100068);
    a.push_back(64228861);
    a.push_back(3388277);
    a.push_back(99400944);
    a.push_back(1652926);
    a.push_back(34292960);
    a.push_back(46917032);
    a.push_back(73287929);
    a.push_back(73251927);
    a.push_back(70801818);
    a.push_back(80974779);
    a.push_back(61997576);
    a.push_back(72227344);
    a.push_back(75185401);
    a.push_back(75859633);
    a.push_back(3723676);
    a.push_back(64306914);
    a.push_back(1028145);
    a.push_back(41385899);
    a.push_back(81321000);
    a.push_back(2039064);
    a.push_back(98092796);
    a.push_back(80350019);
    a.push_back(33698268);
    a.push_back(82911370);
    a.push_back(38015076);
    a.push_back(51069557);
    a.push_back(93217303);
    a.push_back(67407421);
    a.push_back(88203987);
    a.push_back(42511422);
    a.push_back(81344751);
    a.push_back(92492505);
    a.push_back(83655152);
    a.push_back(81736121);
    a.push_back(70792567);
    a.push_back(59438505);
    a.push_back(51045456);
    a.push_back(78031280);
    a.push_back(69450049);
    a.push_back(68462604);
    a.push_back(45152094);
    a.push_back(84008967);
    a.push_back(71911841);
    a.push_back(99482769);
    a.push_back(59803407);
    a.push_back(39197368);
    a.push_back(91306482);
    a.push_back(51986286);
    a.push_back(51986286);
    a.push_back(53596384);
    a.push_back(36499673);
    a.push_back(49715377);
    a.push_back(46315486);
    a.push_back(63650275);
    a.push_back(92492505);
    a.push_back(64525519);
    a.push_back(69145396);
    a.push_back(43604248);
    a.push_back(71394312);
    a.push_back(2687121);
    a.push_back(46374751);
    a.push_back(39806790);
    a.push_back(58871158);
    a.push_back(34590056);
    a.push_back(3110186);
    a.push_back(93698376);
    a.push_back(95136974);
    a.push_back(89793995);
    a.push_back(74839248);
    a.push_back(76804707);
    a.push_back(99149705);
    a.push_back(39910117);
    a.push_back(70855337);
    a.push_back(54135907);
    a.push_back(77020982);
    a.push_back(78664099);
    a.push_back(37791454);
    a.push_back(46116902);
    a.push_back(38786385);
    a.push_back(95245738);
    a.push_back(43552673);
    a.push_back(57317248);
    a.push_back(92254186);
    a.push_back(78485431);
    a.push_back(2472092);
    a.push_back(62410651);
    a.push_back(58100930);
    a.push_back(3635921);
    a.push_back(52401761);
    a.push_back(63644942);
    a.push_back(63060019);
    a.push_back(34700868);
    a.push_back(59085025);
    a.push_back(61790311);
    a.push_back(99225801);
    a.push_back(93965610);
    a.push_back(35415269);
    a.push_back(49264502);
    a.push_back(217869);
    a.push_back(42684826);
    a.push_back(66540805);
    a.push_back(35414130);
    a.push_back(73278468);
    a.push_back(37287375);
    a.push_back(88825835);
    a.push_back(43559845);
    a.push_back(73903480);
    a.push_back(1153257);
    a.push_back(89991541);
    a.push_back(58501356);
    a.push_back(45992500);
    a.push_back(94969014);
    a.push_back(48505368);
    a.push_back(56639199);
    a.push_back(46374751);
    a.push_back(40611109);
    a.push_back(53333648);
    a.push_back(74981643);
    a.push_back(84703371);
    a.push_back(49158229);
    a.push_back(79324607);
    a.push_back(85641473);
    a.push_back(63548174);
    a.push_back(40080937);
    a.push_back(76730243);
    a.push_back(1287575);
    a.push_back(85059854);
    a.push_back(75916679);
    a.push_back(76153773);
    a.push_back(37421148);
    a.push_back(69345236);
    a.push_back(97528379);
    a.push_back(34328606);
    a.push_back(74603570);
    a.push_back(54997094);
    a.push_back(81073102);
    a.push_back(97020160);
    a.push_back(83059134);
    a.push_back(98151784);
    a.push_back(82878057);
    a.push_back(3049994);
    a.push_back(97326321);
    a.push_back(54600024);
    a.push_back(95834526);
    a.push_back(47100068);
    a.push_back(86712119);
    a.push_back(44016549);
    a.push_back(92482079);
    a.push_back(85301623);
    a.push_back(74684773);
    a.push_back(85287411);
    a.push_back(41855137);
    a.push_back(84239060);
    a.push_back(92478458);
    a.push_back(46040943);
    a.push_back(38762328);
    a.push_back(432865);
    a.push_back(35016845);
    a.push_back(53378365);
    a.push_back(41009995);
    a.push_back(75439448);
    a.push_back(89150923);
    a.push_back(74927433);
    a.push_back(73287929);
    a.push_back(72227344);
    a.push_back(48943848);
    a.push_back(57298099);
    a.push_back(93091762);
    a.push_back(82911370);
    a.push_back(46040943);
    a.push_back(88293733);
    a.push_back(34079966);
    a.push_back(47819612);
    a.push_back(42692976);
    a.push_back(45390633);
    a.push_back(56945830);
    a.push_back(37421148);
    a.push_back(80974779);
    a.push_back(54253219);
    a.push_back(89871043);
    a.push_back(89871043);
    a.push_back(91595347);
    a.push_back(55275993);
    a.push_back(98092796);
    a.push_back(87865296);
    a.push_back(98744357);
    a.push_back(40505836);
    a.push_back(56123290);
    a.push_back(60636234);
    a.push_back(92478458);
    a.push_back(72672525);
    a.push_back(74507030);
    a.push_back(88517917);
    a.push_back(55559520);
    a.push_back(50257593);
    a.push_back(73084750);
    a.push_back(42367471);
    a.push_back(61711779);
    a.push_back(78034200);
    a.push_back(91595347);
    a.push_back(68349901);
    a.push_back(41855137);
    a.push_back(41278059);
    a.push_back(42523397);
    a.push_back(97663797);
    a.push_back(64814525);
    a.push_back(64369827);
    a.push_back(80375183);
    a.push_back(85059854);
    a.push_back(1901260);
    a.push_back(55767747);
    a.push_back(78694938);
    a.push_back(64279847);
    a.push_back(67612906);
    a.push_back(95174043);
    a.push_back(38429734);
    a.push_back(81073102);
    a.push_back(88429369);
    a.push_back(57905084);
    a.push_back(62097965);
    a.push_back(81982962);
    a.push_back(65221849);
    a.push_back(54068001);
    a.push_back(82152427);
    a.push_back(62707401);
    a.push_back(50379946);
    a.push_back(54484909);
    a.push_back(59803407);
    a.push_back(73161064);
    a.push_back(39824445);
    a.push_back(81494266);
    a.push_back(2417970);
    a.push_back(648490);
    a.push_back(46201679);
    a.push_back(67069248);
    a.push_back(38437905);
    a.push_back(47449453);
    a.push_back(40505836);
    a.push_back(53432496);
    a.push_back(33698268);
    a.push_back(38762328);
    a.push_back(44408268);
    a.push_back(1871548);
    a.push_back(81494266);
    a.push_back(60374482);
    a.push_back(51013089);
    a.push_back(52833933);
    a.push_back(75439448);
    a.push_back(99657697);
    a.push_back(99019616);
    a.push_back(2895749);
    a.push_back(92150204);
    a.push_back(88796382);
    a.push_back(67005790);
    a.push_back(60811679);
    a.push_back(72191509);
    a.push_back(61062638);
    a.push_back(39910117);
    a.push_back(37287375);
    a.push_back(70850038);
    a.push_back(36646205);
    a.push_back(74162075);
    a.push_back(62410651);
    a.push_back(88172202);
    a.push_back(52705848);
    a.push_back(80690818);
    a.push_back(47923629);
    a.push_back(76804707);
    a.push_back(63548174);
    a.push_back(81982962);
    a.push_back(84231193);
    a.push_back(83059134);
    a.push_back(93048548);
    a.push_back(4617797);
    a.push_back(63060019);
    a.push_back(62099308);
    a.push_back(63564601);
    a.push_back(54125778);
    a.push_back(69450049);
    a.push_back(461313);
    a.push_back(74716695);
    a.push_back(52833933);
    a.push_back(93241936);
    a.push_back(97528379);
    a.push_back(51159332);
    a.push_back(70913710);
    a.push_back(754567);
    a.push_back(70689341);
    a.push_back(92372811);
    a.push_back(66671476);
    a.push_back(81418905);
    a.push_back(95174043);
    a.push_back(64228861);
    a.push_back(53691207);
    a.push_back(47635566);
    a.push_back(61337371);
    a.push_back(39013453);
    a.push_back(81993791);
    a.push_back(36750048);
    a.push_back(48541599);
    a.push_back(1962718);
    a.push_back(42511422);
    a.push_back(90756244);
    a.push_back(98288946);
    a.push_back(59928504);
    a.push_back(67407421);
    a.push_back(80742646);
    a.push_back(58333134);
    a.push_back(98151784);
    a.push_back(1310992);
    a.push_back(74753325);
    a.push_back(38015076);
    a.push_back(55912215);
    a.push_back(77372664);
    a.push_back(3249494);
    a.push_back(55498195);
    a.push_back(60808434);
    a.push_back(67443995);
    a.push_back(45152094);
    a.push_back(57504893);
    a.push_back(93483247);
    a.push_back(94969014);
    a.push_back(54659906);
    a.push_back(68462604);
    a.push_back(69884552);
    a.push_back(37740543);
    a.push_back(99096089);
    a.push_back(66596231);
    a.push_back(47985561);
    a.push_back(62785250);
    a.push_back(94035478);
    a.push_back(52401761);
    a.push_back(55022617);
    a.push_back(79570514);
    a.push_back(95126099);
    a.push_back(84082169);
    a.push_back(42367471);
    a.push_back(40701253);
    a.push_back(98238674);
    a.push_back(3131638);
    a.push_back(83714571);
    a.push_back(62646077);
    a.push_back(75136032);
    a.push_back(79201061);
    a.push_back(71955461);
    a.push_back(48055628);
    a.push_back(84239060);
    a.push_back(80096701);
    a.push_back(46116902);
    a.push_back(94696779);
    a.push_back(95288008);
    a.push_back(49966020);
    a.push_back(54642606);
    a.push_back(80925392);
    a.push_back(34782380);
    a.push_back(80089348);
    a.push_back(87118015);
    a.push_back(62707401);
    a.push_back(70337483);
    a.push_back(93664496);
    a.push_back(97326321);
    a.push_back(64279847);
    a.push_back(81056734);
    a.push_back(98138560);
    a.push_back(75651721);
    a.push_back(60636234);
    a.push_back(57750738);
    a.push_back(97662651);
    a.push_back(61790311);
    a.push_back(46210307);
    a.push_back(54434610);
    a.push_back(89043953);
    a.push_back(43405383);
    a.push_back(98881454);
    a.push_back(43552673);
    a.push_back(93354761);
    a.push_back(67240799);
    a.push_back(85027514);
    a.push_back(79204903);
    a.push_back(94615559);
    a.push_back(56329961);
    a.push_back(33807649);
    a.push_back(55767747);
    a.push_back(62097965);
    a.push_back(81046208);
    a.push_back(89047161);
    a.push_back(60811679);
    a.push_back(3068949);
    a.push_back(37564185);
    a.push_back(61717678);
    a.push_back(59310018);
    a.push_back(35484038);
    a.push_back(955566);
    a.push_back(77372664);
    a.push_back(63858470);
    a.push_back(2598810);
    a.push_back(53002794);
    a.push_back(97902807);
    a.push_back(52705848);
    a.push_back(97652181);
    a.push_back(1493709);
    a.push_back(75663481);
    a.push_back(36750048);
    a.push_back(55996478);
    a.push_back(91883667);
    a.push_back(2529826);
    a.push_back(85059854);
    a.push_back(86366944);
    a.push_back(53919548);
    a.push_back(93163663);
    a.push_back(94035478);
    a.push_back(72191509);
    a.push_back(81344751);
    a.push_back(78806240);
    a.push_back(88136292);
    a.push_back(76804707);
    a.push_back(57704844);
    a.push_back(93839493);
    a.push_back(40505836);
    a.push_back(56427995);
    a.push_back(54362533);
    a.push_back(40738303);
    a.push_back(79092278);
    a.push_back(1083641);
    a.push_back(49306857);
    a.push_back(41385899);
    a.push_back(59696359);
    a.push_back(68662558);
    a.push_back(87073471);
    a.push_back(35420209);
    a.push_back(95518882);
    a.push_back(68281549);
    a.push_back(42578725);
    a.push_back(95100634);
    a.push_back(57488493);
    a.push_back(49715377);
    a.push_back(71615915);
    a.push_back(76878751);
    a.push_back(35007201);
    a.push_back(94035478);
    a.push_back(45272043);
    a.push_back(59589493);
    a.push_back(70801818);
    a.push_back(49400882);
    a.push_back(97023178);
    a.push_back(95126099);
    a.push_back(40705818);
    a.push_back(48228790);
    a.push_back(51722999);
    a.push_back(78493614);
    a.push_back(81475759);
    a.push_back(77455212);
    a.push_back(57581028);
    a.push_back(35414130);
    a.push_back(50379946);
    a.push_back(82811370);
    a.push_back(93473669);
    a.push_back(90756244);
    a.push_back(46315486);
    a.push_back(73603764);
    a.push_back(96514477);
    a.push_back(82878057);
    a.push_back(48735753);
    a.push_back(85641473);
    a.push_back(82467201);
    a.push_back(96514477);
    a.push_back(88769667);
    a.push_back(47140565);
    a.push_back(93319111);
    a.push_back(53378365);
    a.push_back(78143708);
    a.push_back(61790311);
    a.push_back(51069557);
    a.push_back(99482769);
    a.push_back(48228790);
    a.push_back(60563958);
    a.push_back(87388198);
    a.push_back(92872101);
    a.push_back(36787038);
    a.push_back(91670213);
    a.push_back(77484337);
    a.push_back(57474910);
    a.push_back(35420209);
    a.push_back(47449453);
    a.push_back(73693993);
    a.push_back(81982962);
    a.push_back(39910117);
    a.push_back(93208734);
    a.push_back(35484038);
    a.push_back(58329257);
    a.push_back(64369827);
    a.push_back(67612906);
    a.push_back(94526405);
    a.push_back(34988886);
    a.push_back(38550105);
    a.push_back(81993791);
    a.push_back(66596231);
    a.push_back(2387720);
    a.push_back(71579831);
    a.push_back(70337483);
    a.push_back(1181685);
    a.push_back(59905755);
    a.push_back(61456131);
    a.push_back(89361880);
    a.push_back(1192112);
    a.push_back(77549825);
    a.push_back(35348449);
    a.push_back(39806790);
    a.push_back(61744640);
    a.push_back(50187413);
    a.push_back(48701296);
    a.push_back(59393335);
    a.push_back(48487558);
    a.push_back(2648362);
    a.push_back(75227666);
    a.push_back(81494266);
    a.push_back(91883667);
    a.push_back(43008261);
    a.push_back(89328623);
    a.push_back(75651721);
    a.push_back(66150536);
    a.push_back(1749192);
    a.push_back(54642606);
    a.push_back(89487584);
    a.push_back(77399538);
    a.push_back(40866456);
    a.push_back(94526405);
    a.push_back(34079966);
    a.push_back(89566971);
    a.push_back(39197368);
    a.push_back(45362565);
    a.push_back(73239921);
    a.push_back(1978530);
    a.push_back(48541599);
    a.push_back(61477255);
    a.push_back(74927433);
    a.push_back(56634253);
    a.push_back(93241936);
    a.push_back(1128881);
    a.push_back(53919548);
    a.push_back(61442989);
    a.push_back(68987721);
    a.push_back(43604248);
    a.push_back(53943434);
    a.push_back(92800529);
    a.push_back(35566564);
    a.push_back(87971727);
    a.push_back(35368054);
    a.push_back(82203044);
    a.push_back(34782380);
    a.push_back(90164689);
    a.push_back(85567856);
    a.push_back(90360875);
    a.push_back(81824265);
    a.push_back(53378365);
    a.push_back(54125778);
    a.push_back(53324768);
    a.push_back(83823376);
    a.push_back(77155424);
    a.push_back(59515346);
    a.push_back(97540652);
    a.push_back(39197368);
    a.push_back(89150923);
    a.push_back(46447295);
    a.push_back(67443995);
    a.push_back(38015076);
    a.push_back(53822956);
    a.push_back(88202125);
    a.push_back(1232514);
    a.push_back(53596384);
    a.push_back(78956024);
    a.push_back(48228790);
    a.push_back(95100634);
    a.push_back(73302817);
    a.push_back(97023178);
    a.push_back(40281575);
    a.push_back(47604562);
    a.push_back(565659);
    a.push_back(43610110);
    a.push_back(43845581);
    a.push_back(78806240);
    a.push_back(38412604);
    a.push_back(98138560);
    a.push_back(72672525);
    a.push_back(83059134);
    a.push_back(67163481);
    a.push_back(70332336);
    a.push_back(60563958);
    a.push_back(65093300);
    a.push_back(80375183);
    a.push_back(90176846);
    a.push_back(53599508);
    a.push_back(69345236);
    a.push_back(35420209);
    a.push_back(85753067);
    a.push_back(42523397);
    a.push_back(43603185);
    a.push_back(90948330);
    a.push_back(57581028);
    a.push_back(95480236);
    a.push_back(77588731);
    a.push_back(82203044);
    a.push_back(91131123);
    a.push_back(3520257);
    a.push_back(76153773);
    a.push_back(33864776);
    a.push_back(54659906);
    a.push_back(34124878);
    a.push_back(72140401);
    a.push_back(782683);
    a.push_back(62646077);
    a.push_back(4291824);
    a.push_back(43243372);
    a.push_back(48656573);
    a.push_back(56329961);
    a.push_back(48595629);
    a.push_back(87428019);
    a.push_back(2136758);
    a.push_back(58144892);
    a.push_back(73603764);
    a.push_back(62869445);
    a.push_back(94439937);
    a.push_back(81047539);
    a.push_back(54484909);
    a.push_back(38778508);
    a.push_back(61717678);
    a.push_back(53599508);
    a.push_back(39197368);
    a.push_back(42202642);
    a.push_back(38389426);
    a.push_back(95847602);
    a.push_back(68662558);
    a.push_back(34782380);
    a.push_back(40705818);
    a.push_back(99896034);
    a.push_back(80350019);
    a.push_back(58100930);
    a.push_back(42367471);
    a.push_back(1575528);
    a.push_back(854512);
    a.push_back(64644764);
    b.push_back(76730243);
    b.push_back(67069248);
    b.push_back(34988886);
    b.push_back(64369827);
    b.push_back(50379946);
    b.push_back(88963645);
    b.push_back(40281575);
    b.push_back(74716695);
    b.push_back(68662558);
    b.push_back(43968964);
    b.push_back(70332336);
    b.push_back(67069248);
    b.push_back(76804707);
    b.push_back(43008261);
    b.push_back(47140565);
    b.push_back(85753067);
    b.push_back(95847602);
    b.push_back(60563958);
    b.push_back(97326321);
    b.push_back(36750048);
    b.push_back(56329961);
    b.push_back(48228790);
    b.push_back(99019616);
    b.push_back(36646205);
    b.push_back(63644942);
    b.push_back(72140401);
    b.push_back(61744640);
    b.push_back(54434610);
    b.push_back(35415269);
    b.push_back(57750738);
    b.push_back(73287929);
    b.push_back(47819612);
    b.push_back(72140401);
    b.push_back(63060019);
    b.push_back(55912215);
    b.push_back(97540652);
    b.push_back(94696779);
    b.push_back(81982962);
    b.push_back(82203044);
    b.push_back(35484038);
    b.push_back(80089348);
    b.push_back(97020160);
    b.push_back(98138560);
    b.push_back(99200349);
    b.push_back(72672525);
    b.push_back(77155424);
    b.push_back(1692580);
    b.push_back(69634353);
    b.push_back(49158229);
    b.push_back(59085025);
    b.push_back(88203987);
    b.push_back(833570);
    b.push_back(67240799);
    b.push_back(46766908);
    b.push_back(64644764);
    b.push_back(90360875);
    b.push_back(88769667);
    b.push_back(2296501);
    b.push_back(56945830);
    b.push_back(42578725);
    b.push_back(45362565);
    b.push_back(62097965);
    b.push_back(81736121);
    b.push_back(51069557);
    b.push_back(95136974);
    b.push_back(91131123);
    b.push_back(82811370);
    b.push_back(54659906);
    b.push_back(41385899);
    b.push_back(38389426);
    b.push_back(94969014);
    b.push_back(93048548);
    b.push_back(61337371);
    b.push_back(49306857);
    b.push_back(64814525);
    b.push_back(1869142);
    b.push_back(88769667);
    b.push_back(61790311);
    b.push_back(44016549);
    b.push_back(34079966);
    b.push_back(43845581);
    b.push_back(53310394);
    b.push_back(87428019);
    b.push_back(70689341);
    b.push_back(53432496);
    b.push_back(82878057);
    b.push_back(76880320);
    b.push_back(51722999);
    b.push_back(47635566);
    b.push_back(64814525);
    b.push_back(73278468);
    b.push_back(81047539);
    b.push_back(73239921);
    b.push_back(92478458);
    b.push_back(35414130);
    b.push_back(91883667);
    b.push_back(59928504);
    b.push_back(83611418);
    b.push_back(92872101);
    b.push_back(83036137);
    b.push_back(47604562);
    b.push_back(87971727);
    b.push_back(71579831);
    b.push_back(89793995);
    b.push_back(93048548);
    b.push_back(72826360);
    b.push_back(3380985);
    b.push_back(616887);
    b.push_back(81494266);
    b.push_back(59905755);
    b.push_back(1277263);
    b.push_back(205028);
    b.push_back(69145396);
    b.push_back(83473799);
    b.push_back(93163663);
    b.push_back(60811679);
    b.push_back(35420209);
    b.push_back(98474574);
    b.push_back(164366);
    b.push_back(93483247);
    b.push_back(67240799);
    b.push_back(85567856);
    b.push_back(42367471);
    b.push_back(56634253);
    b.push_back(98092796);
    b.push_back(39910117);
    b.push_back(63650275);
    b.push_back(54362533);
    b.push_back(59515346);
    b.push_back(61997576);
    b.push_back(47100068);
    b.push_back(95174043);
    b.push_back(95847602);
    b.push_back(99149705);
    b.push_back(48055628);
    b.push_back(55022617);
    b.push_back(83823376);
    b.push_back(49400882);
    b.push_back(81046208);
    b.push_back(97528379);
    b.push_back(82878057);
    b.push_back(67612906);
    b.push_back(80742646);
    b.push_back(40080937);
    b.push_back(97023178);
    b.push_back(70913710);
    b.push_back(62646077);
    b.push_back(42511422);
    b.push_back(99096089);
    b.push_back(99400944);
    b.push_back(38437905);
    b.push_back(61442989);
    b.push_back(95100634);
    b.push_back(93354761);
    b.push_back(66150536);
    b.push_back(43405383);
    b.push_back(48228790);
    b.push_back(48505368);
    b.push_back(74603570);
    b.push_back(97652181);
    b.push_back(70337483);
    b.push_back(72140401);
    b.push_back(51013089);
    b.push_back(35007201);
    b.push_back(88796382);
    b.push_back(40701253);
    b.push_back(70801818);
    b.push_back(54484909);
    b.push_back(46315486);
    b.push_back(95480236);
    b.push_back(95834526);
    b.push_back(40611109);
    b.push_back(93664496);
    b.push_back(93241936);
    b.push_back(74507030);
    b.push_back(92478458);
    b.push_back(73903480);
    b.push_back(95174043);
    b.push_back(81982962);
    b.push_back(86712119);
    b.push_back(48656573);
    b.push_back(77155424);
    b.push_back(71394312);
    b.push_back(79092278);
    b.push_back(99896034);
    b.push_back(88432110);
    b.push_back(75859633);
    b.push_back(99225801);
    b.push_back(97663797);
    b.push_back(55767747);
    b.push_back(75916679);
    b.push_back(33864776);
    b.push_back(85059854);
    b.push_back(79570514);
    b.push_back(77020982);
    b.push_back(67407421);
    b.push_back(85027514);
    b.push_back(65221849);
    b.push_back(1257020);
    b.push_back(70689341);
    b.push_back(73287929);
    b.push_back(98474574);
    b.push_back(54642606);
    b.push_back(91306482);
    b.push_back(74927433);
    b.push_back(54117396);
    b.push_back(62785250);
    b.push_back(70850038);
    b.push_back(53822956);
    b.push_back(71911841);
    b.push_back(56123290);
    b.push_back(46447295);
    b.push_back(33698268);
    b.push_back(46210307);
    b.push_back(36787038);
    b.push_back(49264502);
    b.push_back(91670213);
    b.push_back(3928656);
    b.push_back(78493614);
    b.push_back(99225801);
    b.push_back(84082169);
    b.push_back(34782380);
    b.push_back(46374751);
    b.push_back(93965610);
    b.push_back(73603764);
    b.push_back(80096701);
    b.push_back(57488493);
    b.push_back(74981643);
    b.push_back(80974779);
    b.push_back(38429734);
    b.push_back(42684826);
    b.push_back(80375183);
    b.push_back(59589493);
    b.push_back(68349901);
    b.push_back(84239060);
    b.push_back(70801818);
    b.push_back(75663481);
    b.push_back(51045456);
    b.push_back(38778508);
    b.push_back(85287411);
    b.push_back(43559845);
    b.push_back(33807649);
    b.push_back(48541599);
    b.push_back(44408268);
    b.push_back(81321000);
    b.push_back(39013453);
    b.push_back(81993791);
    b.push_back(41385899);
    b.push_back(46116902);
    b.push_back(68462604);
    b.push_back(72191509);
    b.push_back(70850038);
    b.push_back(85641473);
    b.push_back(69884552);
    b.push_back(57581028);
    b.push_back(69450049);
    b.push_back(75185401);
    b.push_back(80925392);
    b.push_back(70913710);
    b.push_back(59310018);
    b.push_back(88517917);
    b.push_back(59438505);
    b.push_back(78694938);
    b.push_back(67857444);
    b.push_back(63564601);
    b.push_back(35566564);
    b.push_back(35317490);
    b.push_back(55275993);
    b.push_back(63060019);
    b.push_back(62099308);
    b.push_back(99225801);
    b.push_back(62869445);
    b.push_back(49715377);
    b.push_back(1371940);
    b.push_back(82203044);
    b.push_back(57704844);
    b.push_back(47923629);
    b.push_back(76880320);
    b.push_back(83714571);
    b.push_back(38786385);
    b.push_back(48505368);
    b.push_back(89043953);
    b.push_back(1493587);
    b.push_back(87388198);
    b.push_back(91595347);
    b.push_back(52833933);
    b.push_back(74716695);
    b.push_back(64228861);
    b.push_back(50187413);
    b.push_back(2360730);
    b.push_back(37421148);
    b.push_back(81418905);
    b.push_back(38437905);
    b.push_back(41855137);
    b.push_back(96703184);
    b.push_back(46040943);
    b.push_back(34700868);
    b.push_back(66983362);
    b.push_back(35484038);
    b.push_back(70792567);
    b.push_back(88172202);
    b.push_back(61477255);
    b.push_back(42367471);
    b.push_back(34124878);
    b.push_back(67163481);
    b.push_back(94439937);
    b.push_back(67407421);
    b.push_back(35348449);
    b.push_back(34590056);
    b.push_back(56639199);
    b.push_back(61062638);
    b.push_back(81073102);
    b.push_back(67893661);
    b.push_back(1474866);
    b.push_back(95288008);
    b.push_back(71394312);
    b.push_back(85753067);
    b.push_back(93217303);
    b.push_back(52705848);
    b.push_back(99400944);
    b.push_back(3158950);
    b.push_back(37564185);
    b.push_back(466878);
    b.push_back(98151784);
    b.push_back(82811370);
    b.push_back(2523185);
    b.push_back(38412604);
    b.push_back(60636234);
    b.push_back(41855137);
    b.push_back(62410651);
    b.push_back(43604248);
    b.push_back(89566971);
    b.push_back(51159332);
    b.push_back(853548);
    b.push_back(45272043);
    b.push_back(49966020);
    b.push_back(87865296);
    b.push_back(95518882);
    b.push_back(64951365);
    b.push_back(73302817);
    b.push_back(68349901);
    b.push_back(77549825);
    b.push_back(56639199);
    b.push_back(89047161);
    b.push_back(78485431);
    b.push_back(92492505);
    b.push_back(36499673);
    b.push_back(74162075);
    b.push_back(45390633);
    b.push_back(78143708);
    b.push_back(70855337);
    b.push_back(81475759);
    b.push_back(92800529);
    b.push_back(42202642);
    b.push_back(45390633);
    b.push_back(61711779);
    b.push_back(89150923);
    b.push_back(99019616);
    b.push_back(53002794);
    b.push_back(35007201);
    b.push_back(54135907);
    b.push_back(91131123);
    b.push_back(46040943);
    b.push_back(57317248);
    b.push_back(37564185);
    b.push_back(90176846);
    b.push_back(48487558);
    b.push_back(99657697);
    b.push_back(38762328);
    b.push_back(67443995);
    b.push_back(66150536);
    b.push_back(58871158);
    b.push_back(77399538);
    b.push_back(73278468);
    b.push_back(98138560);
    b.push_back(72227344);
    b.push_back(53919548);
    b.push_back(50868655);
    b.push_back(56634253);
    b.push_back(85027514);
    b.push_back(37287375);
    b.push_back(76878751);
    b.push_back(39197368);
    b.push_back(58667405);
    b.push_back(50257593);
    b.push_back(41278059);
    b.push_back(95245738);
    b.push_back(92254186);
    b.push_back(37287375);
    b.push_back(84239060);
    b.push_back(89871043);
    b.push_back(35317490);
    b.push_back(93473669);
    b.push_back(80599);
    b.push_back(37740543);
    b.push_back(93698376);
    b.push_back(76878751);
    b.push_back(43610110);
    b.push_back(53943434);
    b.push_back(81982962);
    b.push_back(98881454);
    b.push_back(64369827);
    b.push_back(38437905);
    b.push_back(46922251);
    b.push_back(87428019);
    b.push_back(89487584);
    b.push_back(87073471);
    b.push_back(34328606);
    b.push_back(75439448);
    b.push_back(70649162);
    b.push_back(77455212);
    b.push_back(83611418);
    b.push_back(59085025);
    b.push_back(90756244);
    b.push_back(83473799);
    b.push_back(40281575);
    b.push_back(40866456);
    b.push_back(44408268);
    b.push_back(53943434);
    b.push_back(48701296);
    b.push_back(99657697);
    b.push_back(72672525);
    b.push_back(73161064);
    b.push_back(97652181);
    b.push_back(39824445);
    b.push_back(88429369);
    b.push_back(49158229);
    b.push_back(64306914);
    b.push_back(59928504);
    b.push_back(42692976);
    b.push_back(38550105);
    b.push_back(53324768);
    b.push_back(63650275);
    b.push_back(88203987);
    b.push_back(57504893);
    b.push_back(868370);
    b.push_back(97662651);
    b.push_back(84703371);
    b.push_back(36750048);
    b.push_back(89566971);
    b.push_back(58144892);
    b.push_back(54597733);
    b.push_back(4277835);
    b.push_back(66671476);
    b.push_back(43243372);
    b.push_back(37791454);
    b.push_back(38015076);
    b.push_back(52401761);
    b.push_back(63858470);
    b.push_back(75227666);
    b.push_back(88136292);
    b.push_back(87388198);
    b.push_back(58329257);
    b.push_back(36499673);
    b.push_back(54997094);
    b.push_back(72714394);
    b.push_back(87865296);
    b.push_back(41278059);
    b.push_back(49264502);
    b.push_back(69345236);
    b.push_back(2713169);
    b.push_back(48595629);
    b.push_back(40738303);
    b.push_back(48735753);
    b.push_back(3184736);
    b.push_back(56427995);
    b.push_back(61456131);
    b.push_back(99482769);
    b.push_back(40611109);
    b.push_back(71955461);
    b.push_back(45992500);
    b.push_back(53596384);
    b.push_back(48487558);
    b.push_back(98345170);
    b.push_back(74839248);
    b.push_back(78656139);
    b.push_back(59438505);
    b.push_back(298028);
    b.push_back(93091762);
    b.push_back(95518882);
    b.push_back(865730);
    b.push_back(78485431);
    b.push_back(59784243);
    b.push_back(71284477);
    b.push_back(43552673);
    b.push_back(85641473);
    b.push_back(534728);
    b.push_back(39102507);
    b.push_back(80720190);
    b.push_back(3631150);
    b.push_back(83059134);
    b.push_back(81056734);
    b.push_back(68462604);
    b.push_back(79204903);
    b.push_back(59696359);
    b.push_back(66596231);
    b.push_back(59393335);
    b.push_back(39806790);
    b.push_back(35566564);
    b.push_back(48943848);
    b.push_back(53378365);
    b.push_back(54600024);
    b.push_back(42523397);
    b.push_back(2757174);
    b.push_back(53378365);
    b.push_back(65221849);
    b.push_back(34590056);
    b.push_back(51986286);
    b.push_back(89047161);
    b.push_back(98744357);
    b.push_back(35420209);
    b.push_back(83823376);
    b.push_back(80089348);
    b.push_back(44204114);
    b.push_back(996142);
    b.push_back(64525519);
    b.push_back(74545376);
    b.push_back(59438505);
    b.push_back(47449453);
    b.push_back(83655152);
    b.push_back(34292960);
    b.push_back(55996478);
    b.push_back(88796382);
    b.push_back(547784);
    b.push_back(53943434);
    b.push_back(642104);
    b.push_back(35016845);
    b.push_back(56123290);
    b.push_back(52705848);
    b.push_back(79201061);
    b.push_back(69684256);
    b.push_back(97020160);
    b.push_back(59515346);
    b.push_back(58501356);
    b.push_back(67443995);
    b.push_back(72227344);
    b.push_back(77588731);
    b.push_back(67857444);
    b.push_back(59085025);
    b.push_back(38015076);
    b.push_back(74839248);
    b.push_back(34079966);
    b.push_back(89361880);
    b.push_back(63858470);
    b.push_back(66540805);
    b.push_back(81824265);
    b.push_back(63766349);
    b.push_back(93839493);
    b.push_back(40072500);
    b.push_back(84231193);
    b.push_back(93839493);
    b.push_back(1167914);
    b.push_back(92482079);
    b.push_back(89991541);
    b.push_back(40919789);
    b.push_back(59803407);
    b.push_back(42578725);
    b.push_back(1819167);
    b.push_back(3531560);
    b.push_back(73302817);
    b.push_back(35414130);
    b.push_back(62707401);
    b.push_back(48055628);
    b.push_back(85301623);
    b.push_back(47985561);
    b.push_back(1102433);
    b.push_back(89361880);
    b.push_back(80690818);
    b.push_back(82467201);
    b.push_back(53691207);
    b.push_back(94035478);
    b.push_back(86366944);
    b.push_back(56599734);
    b.push_back(58871158);
    b.push_back(57474910);
    b.push_back(74753325);
    b.push_back(91614958);
    b.push_back(54434610);
    b.push_back(35348449);
    b.push_back(40505836);
    b.push_back(67005790);
    b.push_back(78664099);
    b.push_back(69684256);
    b.push_back(95245738);
    b.push_back(59803407);
    b.push_back(85059854);
    b.push_back(45152094);
    b.push_back(73693993);
    b.push_back(68987721);
    b.push_back(61717678);
    b.push_back(97902807);
    b.push_back(64279847);
    b.push_back(75136032);
    b.push_back(34225686);
    b.push_back(3960601);
    b.push_back(74716695);
    b.push_back(95126099);
    b.push_back(84231193);
    b.push_back(3352618);
    b.push_back(61456131);
    b.push_back(4470650);
    b.push_back(55559520);
    b.push_back(73287929);
    b.push_back(90756244);
    b.push_back(49966020);
    b.push_back(65093300);
    b.push_back(81824265);
    b.push_back(1111669);
    b.push_back(92880627);
    b.push_back(40701253);
    b.push_back(99200349);
    b.push_back(434814);
    b.push_back(68987721);
    b.push_back(34124878);
    b.push_back(60374482);
    b.push_back(93217303);
    b.push_back(47923629);
    b.push_back(98288946);
    b.push_back(58333134);
    b.push_back(37740543);
    b.push_back(46917032);
    b.push_back(33807649);
    b.push_back(93319111);
    b.push_back(77484337);
    b.push_back(69884552);
    b.push_back(66540805);
    b.push_back(46201679);
    b.push_back(2076049);
    b.push_back(48595629);
    b.push_back(53333648);
    b.push_back(92150204);
    b.push_back(74684773);
    b.push_back(88202125);
    b.push_back(67443995);
    b.push_back(87118015);
    b.push_back(83473799);
    b.push_back(54068001);
    b.push_back(57905084);
    b.push_back(53599508);
    b.push_back(78034200);
    b.push_back(92880627);
    b.push_back(65951);
    b.push_back(71615915);
    b.push_back(97020160);
    b.push_back(48505368);
    b.push_back(58100930);
    b.push_back(60811679);
    b.push_back(73251927);
    b.push_back(75651721);
    b.push_back(42684826);
    b.push_back(87783379);
    b.push_back(34079966);
    b.push_back(87783379);
    b.push_back(78034200);
    b.push_back(43603185);
    b.push_back(54125778);
    b.push_back(55275993);
    b.push_back(48487558);
    b.push_back(90164689);
    b.push_back(46315486);
    b.push_back(1134167);
    b.push_back(93208734);
    b.push_back(8525523);
    b.push_back(48943848);
    b.push_back(84008967);
    b.push_back(89859115);
    b.push_back(1318008);
    b.push_back(63548174);
    b.push_back(54253219);
    b.push_back(70337483);
    b.push_back(56123290);
    b.push_back(84008967);
    b.push_back(90176846);
    b.push_back(73603764);
    b.push_back(81344751);
    b.push_back(57298099);
    b.push_back(53002794);
    b.push_back(51986286);
    b.push_back(76153773);
    b.push_back(89328623);
    b.push_back(88432110);
    b.push_back(57488493);
    b.push_back(78031280);
    b.push_back(95100634);
    b.push_back(38550105);
    b.push_back(45152094);
    b.push_back(3193613);
    b.push_back(73084750);
    b.push_back(98238674);
    b.push_back(60563958);
    b.push_back(90948330);
    b.push_back(96514477);
    b.push_back(92372811);
    b.push_back(46922251);
    b.push_back(99482769);
    b.push_back(61997576);
    b.push_back(56329961);
    b.push_back(40705818);
    b.push_back(96514477);
    b.push_back(83036137);
    b.push_back(73903480);
    b.push_back(78956024);
    b.push_back(62253863);
    b.push_back(49966020);
    b.push_back(58100930);
    b.push_back(945348);
    b.push_back(79324607);
    b.push_back(80350019);
    b.push_back(95480236);
    b.push_back(88293733);
    b.push_back(58144892);
    b.push_back(94845200);
    b.push_back(77372664);
    b.push_back(73251927);
    b.push_back(54659906);
    b.push_back(69345236);
    b.push_back(65093300);
    b.push_back(54642606);
    b.push_back(54253219);
    b.push_back(55498195);
    b.push_back(78143708);
    b.push_back(85301623);
    b.push_back(51013089);
    b.push_back(63060019);
    b.push_back(86366944);
    b.push_back(41009995);
    b.push_back(61442989);
    b.push_back(1152853);
    b.push_back(35368054);
    b.push_back(34292960);
    b.push_back(94615559);
    b.push_back(55022617);
    b.push_back(88825835);
    b.push_back(60808434);
    b.push_back(51045456);
    b.push_back(70332336);
    b.push_back(47449453);
    b.push_back(47985561);
    b.push_back(82152427);
    b.push_back(82911370);
    b.push_back(93698376);
    b.push_back(59085025);
    b.push_back(89043953);
    b.push_back(73693993);
    b.push_back(60374482);
    b.push_back(85027514);
    b.push_back(95804869);
    b.push_back(71394312);
    b.push_back(60563958);
    b.push_back(68281549);
    b.push_back(95245738);
    b.push_back(40281575);
    b.push_back(94526405);
 }

 if (atoi(argv[1]) == 22) {
    N = 1000000000;
    S = 886608704;
    T = 71977630;
    a.push_back(65);
    a.push_back(38);
    a.push_back(73);
    a.push_back(82);
    a.push_back(73);
    a.push_back(470319329);
    a.push_back(59);
    a.push_back(1458238);
    a.push_back(88);
    a.push_back(52);
    a.push_back(13);
    a.push_back(641159602);
    a.push_back(791610351);
    a.push_back(340319996);
    a.push_back(651615279);
    a.push_back(640482722);
    a.push_back(752610784);
    a.push_back(86);
    a.push_back(41);
    a.push_back(87);
    a.push_back(72);
    a.push_back(55);
    a.push_back(970819177);
    a.push_back(26);
    a.push_back(25);
    a.push_back(34);
    a.push_back(76);
    a.push_back(12);
    a.push_back(22);
    a.push_back(90);
    a.push_back(548347786);
    a.push_back(30);
    a.push_back(25);
    a.push_back(10);
    a.push_back(83);
    a.push_back(45);
    a.push_back(10);
    a.push_back(90);
    a.push_back(29);
    a.push_back(98);
    a.push_back(67);
    a.push_back(7);
    a.push_back(19);
    a.push_back(2);
    a.push_back(42);
    a.push_back(14);
    a.push_back(755706041);
    a.push_back(76);
    a.push_back(39);
    a.push_back(522285626);
    a.push_back(542095540);
    a.push_back(450485884);
    a.push_back(35);
    a.push_back(446146727);
    a.push_back(72);
    a.push_back(34);
    a.push_back(35);
    a.push_back(540757859);
    a.push_back(819905080);
    a.push_back(498833636);
    a.push_back(901294611);
    a.push_back(80);
    a.push_back(910267988);
    a.push_back(41);
    a.push_back(9);
    a.push_back(21);
    a.push_back(53);
    a.push_back(52);
    a.push_back(1);
    a.push_back(85);
    a.push_back(2);
    a.push_back(397142389);
    a.push_back(59);
    a.push_back(651615279);
    a.push_back(69);
    a.push_back(372151930);
    a.push_back(1);
    a.push_back(58);
    a.push_back(76);
    a.push_back(5);
    a.push_back(50);
    a.push_back(59);
    a.push_back(872956663);
    a.push_back(72);
    a.push_back(97);
    a.push_back(984563859);
    a.push_back(2);
    a.push_back(551627224);
    a.push_back(511469458);
    a.push_back(40);
    a.push_back(58);
    a.push_back(13);
    a.push_back(479894255);
    a.push_back(61);
    a.push_back(828887110);
    a.push_back(84);
    a.push_back(82);
    a.push_back(72);
    a.push_back(62);
    a.push_back(66);
    a.push_back(26);
    a.push_back(60);
    a.push_back(60);
    a.push_back(45);
    a.push_back(4);
    a.push_back(34);
    a.push_back(40);
    a.push_back(41);
    a.push_back(706405491);
    a.push_back(647394107);
    a.push_back(62);
    a.push_back(16);
    a.push_back(992366084);
    a.push_back(92);
    a.push_back(861182403);
    a.push_back(573844639);
    a.push_back(52);
    a.push_back(85);
    a.push_back(436436035);
    a.push_back(75);
    a.push_back(44);
    a.push_back(21);
    a.push_back(67);
    a.push_back(965932642);
    a.push_back(901294611);
    a.push_back(73);
    a.push_back(744839105);
    a.push_back(501781279);
    a.push_back(50);
    a.push_back(94);
    a.push_back(53);
    a.push_back(89);
    a.push_back(87);
    a.push_back(26);
    a.push_back(50);
    a.push_back(15);
    a.push_back(924800822);
    a.push_back(83);
    a.push_back(45);
    a.push_back(42);
    a.push_back(21);
    a.push_back(33);
    a.push_back(437569637);
    a.push_back(77);
    a.push_back(367527732);
    a.push_back(57);
    a.push_back(1);
    a.push_back(80);
    a.push_back(27);
    a.push_back(837766166);
    a.push_back(548347786);
    a.push_back(706405491);
    a.push_back(94);
    a.push_back(76);
    a.push_back(75);
    a.push_back(100);
    a.push_back(837766166);
    a.push_back(70);
    a.push_back(56);
    a.push_back(919719821);
    a.push_back(12);
    a.push_back(758083839);
    a.push_back(819905080);
    a.push_back(55);
    a.push_back(859400619);
    a.push_back(600696322);
    a.push_back(85);
    a.push_back(67);
    a.push_back(1);
    a.push_back(719946154);
    a.push_back(850200637);
    a.push_back(612789418);
    a.push_back(978065606);
    a.push_back(55);
    a.push_back(52);
    a.push_back(917432617);
    a.push_back(367527732);
    a.push_back(67);
    a.push_back(65);
    a.push_back(550908326);
    a.push_back(4);
    a.push_back(82);
    a.push_back(45);
    a.push_back(47);
    a.push_back(67);
    a.push_back(69);
    a.push_back(551262676);
    a.push_back(46);
    a.push_back(35);
    a.push_back(13);
    a.push_back(647394107);
    a.push_back(81);
    a.push_back(72);
    a.push_back(21);
    a.push_back(83);
    a.push_back(10);
    a.push_back(814262415);
    a.push_back(97);
    a.push_back(376818690);
    a.push_back(853422214);
    a.push_back(42);
    a.push_back(546044502);
    a.push_back(30);
    a.push_back(915522055);
    a.push_back(910267988);
    a.push_back(557094501);
    a.push_back(415161165);
    a.push_back(874736891);
    a.push_back(503848911);
    a.push_back(97);
    a.push_back(769094657);
    a.push_back(693786981);
    a.push_back(583464637);
    a.push_back(415161165);
    a.push_back(500362374);
    a.push_back(4);
    a.push_back(8);
    a.push_back(9);
    a.push_back(475148622);
    a.push_back(31);
    a.push_back(77);
    a.push_back(551262676);
    a.push_back(28);
    a.push_back(17);
    a.push_back(991634055);
    a.push_back(767452426);
    a.push_back(20);
    a.push_back(519088364);
    a.push_back(503038780);
    a.push_back(2);
    a.push_back(88);
    a.push_back(17);
    a.push_back(39);
    a.push_back(620064541);
    a.push_back(14);
    a.push_back(90);
    a.push_back(989782501);
    a.push_back(396499165);
    a.push_back(31);
    a.push_back(52);
    a.push_back(58);
    a.push_back(3);
    a.push_back(97);
    a.push_back(23);
    a.push_back(22);
    a.push_back(34);
    a.push_back(538716010);
    a.push_back(628643571);
    a.push_back(845881031);
    a.push_back(25);
    a.push_back(754697055);
    a.push_back(64);
    a.push_back(551627224);
    a.push_back(745734704);
    a.push_back(401516789);
    a.push_back(345228555);
    a.push_back(72);
    a.push_back(11);
    a.push_back(799713548);
    a.push_back(35);
    a.push_back(20);
    a.push_back(21);
    a.push_back(46);
    a.push_back(560597057);
    a.push_back(31);
    a.push_back(98);
    a.push_back(69);
    a.push_back(33);
    a.push_back(575954861);
    a.push_back(347055772);
    a.push_back(86);
    a.push_back(14);
    a.push_back(5);
    a.push_back(98);
    a.push_back(93);
    a.push_back(61);
    a.push_back(754697055);
    a.push_back(23);
    a.push_back(859373864);
    a.push_back(589234987);
    a.push_back(96);
    a.push_back(13);
    a.push_back(63);
    a.push_back(520370908);
    a.push_back(462236495);
    a.push_back(28);
    a.push_back(79);
    a.push_back(31);
    a.push_back(649977296);
    a.push_back(34);
    a.push_back(52);
    a.push_back(48);
    a.push_back(39);
    a.push_back(64);
    a.push_back(43);
    a.push_back(46);
    a.push_back(8);
    a.push_back(719445848);
    a.push_back(97);
    a.push_back(35);
    a.push_back(33);
    a.push_back(28);
    a.push_back(70);
    a.push_back(395017335);
    a.push_back(22);
    a.push_back(72);
    a.push_back(56);
    a.push_back(932187253);
    a.push_back(636220466);
    a.push_back(501781279);
    a.push_back(63);
    a.push_back(80);
    a.push_back(683901864);
    a.push_back(77);
    a.push_back(100);
    a.push_back(15);
    a.push_back(69);
    a.push_back(99);
    a.push_back(30);
    a.push_back(24);
    a.push_back(487133410);
    a.push_back(81);
    a.push_back(374609488);
    a.push_back(788250970);
    a.push_back(81);
    a.push_back(640288269);
    a.push_back(569178650);
    a.push_back(12);
    a.push_back(77);
    a.push_back(33);
    a.push_back(4);
    a.push_back(17);
    a.push_back(773300700);
    a.push_back(77);
    a.push_back(36);
    a.push_back(534192838);
    a.push_back(693786981);
    a.push_back(569178650);
    a.push_back(991634055);
    a.push_back(56);
    a.push_back(32);
    a.push_back(100);
    a.push_back(22);
    a.push_back(52);
    a.push_back(76);
    a.push_back(991770911);
    a.push_back(352120304);
    a.push_back(857585573);
    a.push_back(8);
    a.push_back(82);
    a.push_back(37);
    a.push_back(744839105);
    a.push_back(61);
    a.push_back(680885374);
    a.push_back(8);
    a.push_back(863232554);
    a.push_back(79);
    a.push_back(40);
    a.push_back(43);
    a.push_back(22);
    a.push_back(70);
    a.push_back(97);
    a.push_back(938310901);
    a.push_back(436639506);
    a.push_back(38);
    a.push_back(991770911);
    a.push_back(589234987);
    a.push_back(471793369);
    a.push_back(70);
    a.push_back(88);
    a.push_back(4);
    a.push_back(29);
    a.push_back(845436198);
    a.push_back(74);
    a.push_back(550908326);
    a.push_back(92);
    a.push_back(433157832);
    a.push_back(2);
    a.push_back(643124856);
    a.push_back(27);
    a.push_back(63);
    a.push_back(36);
    a.push_back(500404448);
    a.push_back(932187253);
    a.push_back(861968872);
    a.push_back(100);
    a.push_back(34);
    a.push_back(969190758);
    a.push_back(99);
    a.push_back(836161663);
    a.push_back(987558875);
    a.push_back(937433095);
    a.push_back(93);
    a.push_back(12);
    a.push_back(69);
    a.push_back(81);
    a.push_back(55);
    a.push_back(51);
    a.push_back(89);
    a.push_back(24);
    a.push_back(937433095);
    a.push_back(582115164);
    a.push_back(863232554);
    a.push_back(39);
    a.push_back(60);
    a.push_back(99);
    a.push_back(570352228);
    a.push_back(79);
    a.push_back(97);
    a.push_back(53);
    a.push_back(81);
    a.push_back(65);
    a.push_back(92);
    a.push_back(859171275);
    a.push_back(548347786);
    a.push_back(522285626);
    a.push_back(68);
    a.push_back(503848911);
    a.push_back(27);
    a.push_back(857735117);
    a.push_back(53);
    a.push_back(77);
    a.push_back(846273171);
    a.push_back(15);
    a.push_back(58);
    a.push_back(19);
    a.push_back(16);
    a.push_back(29);
    a.push_back(29);
    a.push_back(47);
    a.push_back(64);
    a.push_back(996913758);
    a.push_back(88);
    a.push_back(17);
    a.push_back(98);
    a.push_back(924800822);
    a.push_back(512132280);
    a.push_back(92);
    a.push_back(56);
    a.push_back(6);
    a.push_back(570352228);
    a.push_back(762895019);
    a.push_back(872956663);
    a.push_back(59);
    a.push_back(72);
    a.push_back(46);
    a.push_back(18);
    a.push_back(669109562);
    a.push_back(35);
    a.push_back(554349628);
    a.push_back(859373864);
    a.push_back(41);
    a.push_back(54);
    a.push_back(23);
    a.push_back(56);
    a.push_back(51);
    a.push_back(782114504);
    a.push_back(95);
    a.push_back(99);
    a.push_back(41);
    a.push_back(24);
    a.push_back(27);
    a.push_back(84);
    a.push_back(3);
    a.push_back(333934634);
    a.push_back(23);
    a.push_back(23);
    a.push_back(41);
    a.push_back(66);
    a.push_back(30);
    a.push_back(722607871);
    a.push_back(63);
    a.push_back(644683661);
    a.push_back(94);
    a.push_back(26);
    a.push_back(8);
    a.push_back(80);
    a.push_back(985960968);
    a.push_back(510073471);
    a.push_back(753640303);
    a.push_back(345832336);
    a.push_back(866070336);
    a.push_back(501129199);
    a.push_back(13);
    a.push_back(23);
    a.push_back(85);
    a.push_back(420520602);
    a.push_back(100);
    a.push_back(811184980);
    a.push_back(387023621);
    a.push_back(8);
    a.push_back(85);
    a.push_back(873655122);
    a.push_back(515069790);
    a.push_back(497683194);
    a.push_back(11);
    a.push_back(924800822);
    a.push_back(33);
    a.push_back(37);
    a.push_back(52);
    a.push_back(39);
    a.push_back(71);
    a.push_back(71);
    a.push_back(752607791);
    a.push_back(48);
    a.push_back(500113859);
    a.push_back(10);
    a.push_back(985960968);
    a.push_back(600696322);
    a.push_back(92);
    a.push_back(585772189);
    a.push_back(849886929);
    a.push_back(861182403);
    a.push_back(712765546);
    a.push_back(55);
    a.push_back(55);
    a.push_back(471793369);
    a.push_back(78);
    a.push_back(71);
    a.push_back(503451416);
    a.push_back(8);
    a.push_back(32);
    a.push_back(334303236);
    a.push_back(70);
    a.push_back(16);
    a.push_back(95);
    a.push_back(74);
    a.push_back(10);
    a.push_back(436436035);
    a.push_back(45);
    a.push_back(376818690);
    a.push_back(99);
    a.push_back(340319996);
    b.push_back(80);
    b.push_back(31);
    b.push_back(43);
    b.push_back(33);
    b.push_back(15);
    b.push_back(628643571);
    b.push_back(83);
    b.push_back(758083839);
    b.push_back(4);
    b.push_back(21);
    b.push_back(2);
    b.push_back(437569637);
    b.push_back(641159602);
    b.push_back(401516789);
    b.push_back(519088364);
    b.push_back(585772189);
    b.push_back(501781279);
    b.push_back(57);
    b.push_back(8);
    b.push_back(88);
    b.push_back(79);
    b.push_back(61);
    b.push_back(762895019);
    b.push_back(56);
    b.push_back(86);
    b.push_back(74);
    b.push_back(46);
    b.push_back(9);
    b.push_back(47);
    b.push_back(79);
    b.push_back(515069790);
    b.push_back(21);
    b.push_back(31);
    b.push_back(9);
    b.push_back(61);
    b.push_back(44);
    b.push_back(35);
    b.push_back(13);
    b.push_back(80);
    b.push_back(88);
    b.push_back(37);
    b.push_back(33);
    b.push_back(10);
    b.push_back(78);
    b.push_back(60);
    b.push_back(98);
    b.push_back(649977296);
    b.push_back(86);
    b.push_back(97);
    b.push_back(846273171);
    b.push_back(991634055);
    b.push_back(863232554);
    b.push_back(85);
    b.push_back(644683661);
    b.push_back(39);
    b.push_back(26);
    b.push_back(41);
    b.push_back(519088364);
    b.push_back(866070336);
    b.push_back(415161165);
    b.push_back(497683194);
    b.push_back(38);
    b.push_back(446146727);
    b.push_back(85);
    b.push_back(51);
    b.push_back(78);
    b.push_back(27);
    b.push_back(41);
    b.push_back(29);
    b.push_back(10);
    b.push_back(29);
    b.push_back(395017335);
    b.push_back(49);
    b.push_back(540757859);
    b.push_back(9);
    b.push_back(680885374);
    b.push_back(42);
    b.push_back(90);
    b.push_back(19);
    b.push_back(50);
    b.push_back(73);
    b.push_back(38);
    b.push_back(938310901);
    b.push_back(92);
    b.push_back(54);
    b.push_back(538716010);
    b.push_back(8);
    b.push_back(970819177);
    b.push_back(450485884);
    b.push_back(3);
    b.push_back(56);
    b.push_back(18);
    b.push_back(917432617);
    b.push_back(23);
    b.push_back(554349628);
    b.push_back(45);
    b.push_back(20);
    b.push_back(74);
    b.push_back(30);
    b.push_back(38);
    b.push_back(3);
    b.push_back(71);
    b.push_back(99);
    b.push_back(57);
    b.push_back(41);
    b.push_back(37);
    b.push_back(66);
    b.push_back(33);
    b.push_back(984563859);
    b.push_back(850200637);
    b.push_back(8);
    b.push_back(62);
    b.push_back(836161663);
    b.push_back(19);
    b.push_back(446146727);
    b.push_back(498833636);
    b.push_back(46);
    b.push_back(99);
    b.push_back(583464637);
    b.push_back(1);
    b.push_back(18);
    b.push_back(24);
    b.push_back(27);
    b.push_back(712765546);
    b.push_back(387023621);
    b.push_back(16);
    b.push_back(612789418);
    b.push_back(550908326);
    b.push_back(40);
    b.push_back(51);
    b.push_back(4);
    b.push_back(95);
    b.push_back(7);
    b.push_back(1);
    b.push_back(99);
    b.push_back(17);
    b.push_back(550908326);
    b.push_back(21);
    b.push_back(80);
    b.push_back(54);
    b.push_back(11);
    b.push_back(3);
    b.push_back(520370908);
    b.push_back(40);
    b.push_back(866070336);
    b.push_back(38);
    b.push_back(74);
    b.push_back(44);
    b.push_back(73);
    b.push_back(640288269);
    b.push_back(752607791);
    b.push_back(859400619);
    b.push_back(6);
    b.push_back(48);
    b.push_back(29);
    b.push_back(79);
    b.push_back(340319996);
    b.push_back(14);
    b.push_back(97);
    b.push_back(845436198);
    b.push_back(77);
    b.push_back(471793369);
    b.push_back(367527732);
    b.push_back(69);
    b.push_back(984563859);
    b.push_back(644683661);
    b.push_back(71);
    b.push_back(52);
    b.push_back(59);
    b.push_back(475148622);
    b.push_back(978065606);
    b.push_back(969190758);
    b.push_back(372151930);
    b.push_back(60);
    b.push_back(35);
    b.push_back(861968872);
    b.push_back(560597057);
    b.push_back(55);
    b.push_back(32);
    b.push_back(965932642);
    b.push_back(67);
    b.push_back(98);
    b.push_back(32);
    b.push_back(65);
    b.push_back(85);
    b.push_back(57);
    b.push_back(510073471);
    b.push_back(57);
    b.push_back(16);
    b.push_back(74);
    b.push_back(396499165);
    b.push_back(91);
    b.push_back(70);
    b.push_back(53);
    b.push_back(91);
    b.push_back(78);
    b.push_back(992366084);
    b.push_back(26);
    b.push_back(752607791);
    b.push_back(470319329);
    b.push_back(5);
    b.push_back(769094657);
    b.push_back(71);
    b.push_back(500362374);
    b.push_back(644683661);
    b.push_back(873655122);
    b.push_back(479894255);
    b.push_back(859373864);
    b.push_back(551627224);
    b.push_back(67);
    b.push_back(573844639);
    b.push_back(436639506);
    b.push_back(788250970);
    b.push_back(917432617);
    b.push_back(512132280);
    b.push_back(26);
    b.push_back(71);
    b.push_back(67);
    b.push_back(996913758);
    b.push_back(46);
    b.push_back(30);
    b.push_back(745734704);
    b.push_back(58);
    b.push_back(11);
    b.push_back(782114504);
    b.push_back(755706041);
    b.push_back(19);
    b.push_back(849886929);
    b.push_back(754697055);
    b.push_back(44);
    b.push_back(20);
    b.push_back(49);
    b.push_back(10);
    b.push_back(932187253);
    b.push_back(72);
    b.push_back(100);
    b.push_back(791610351);
    b.push_back(850200637);
    b.push_back(97);
    b.push_back(90);
    b.push_back(25);
    b.push_back(34);
    b.push_back(14);
    b.push_back(80);
    b.push_back(17);
    b.push_back(9);
    b.push_back(503038780);
    b.push_back(352120304);
    b.push_back(462236495);
    b.push_back(47);
    b.push_back(932187253);
    b.push_back(15);
    b.push_back(693786981);
    b.push_back(510073471);
    b.push_back(551627224);
    b.push_back(487133410);
    b.push_back(37);
    b.push_back(50);
    b.push_back(965932642);
    b.push_back(31);
    b.push_back(21);
    b.push_back(83);
    b.push_back(95);
    b.push_back(333934634);
    b.push_back(76);
    b.push_back(49);
    b.push_back(96);
    b.push_back(57);
    b.push_back(589234987);
    b.push_back(374609488);
    b.push_back(43);
    b.push_back(39);
    b.push_back(22);
    b.push_back(56);
    b.push_back(58);
    b.push_back(29);
    b.push_back(620064541);
    b.push_back(97);
    b.push_back(919719821);
    b.push_back(996913758);
    b.push_back(20);
    b.push_back(53);
    b.push_back(96);
    b.push_back(828887110);
    b.push_back(436436035);
    b.push_back(88);
    b.push_back(81);
    b.push_back(79);
    b.push_back(23810);
    b.push_back(7);
    b.push_back(34);
    b.push_back(62);
    b.push_back(16);
    b.push_back(29);
    b.push_back(6);
    b.push_back(20);
    b.push_back(4);
    b.push_back(397142389);
    b.push_back(63);
    b.push_back(59);
    b.push_back(95);
    b.push_back(80);
    b.push_back(27);
    b.push_back(334303236);
    b.push_back(85);
    b.push_back(53);
    b.push_back(55);
    b.push_back(542095540);
    b.push_back(503451416);
    b.push_back(924800822);
    b.push_back(2);
    b.push_back(84);
    b.push_back(753640303);
    b.push_back(69);
    b.push_back(5);
    b.push_back(20);
    b.push_back(90);
    b.push_back(67);
    b.push_back(88);
    b.push_back(16);
    b.push_back(901294611);
    b.push_back(83);
    b.push_back(647394107);
    b.push_back(773300700);
    b.push_back(81);
    b.push_back(345832336);
    b.push_back(722607871);
    b.push_back(57);
    b.push_back(35);
    b.push_back(87);
    b.push_back(34);
    b.push_back(47);
    b.push_back(861182403);
    b.push_back(12);
    b.push_back(16);
    b.push_back(636220466);
    b.push_back(683901864);
    b.push_back(752610784);
    b.push_back(500113859);
    b.push_back(63);
    b.push_back(45);
    b.push_back(41);
    b.push_back(67);
    b.push_back(99);
    b.push_back(5);
    b.push_back(938310901);
    b.push_back(582115164);
    b.push_back(837766166);
    b.push_back(97);
    b.push_back(82);
    b.push_back(15);
    b.push_back(969190758);
    b.push_back(13);
    b.push_back(522285626);
    b.push_back(13);
    b.push_back(845881031);
    b.push_back(9);
    b.push_back(26);
    b.push_back(8);
    b.push_back(79);
    b.push_back(5);
    b.push_back(29);
    b.push_back(706405491);
    b.push_back(683901864);
    b.push_back(53);
    b.push_back(857735117);
    b.push_back(719946154);
    b.push_back(985960968);
    b.push_back(10);
    b.push_back(12);
    b.push_back(46);
    b.push_back(15);
    b.push_back(570352228);
    b.push_back(4);
    b.push_back(799713548);
    b.push_back(32);
    b.push_back(744839105);
    b.push_back(23);
    b.push_back(551262676);
    b.push_back(74);
    b.push_back(40);
    b.push_back(58);
    b.push_back(575954861);
    b.push_back(991634055);
    b.push_back(814262415);
    b.push_back(73);
    b.push_back(62);
    b.push_back(819905080);
    b.push_back(28);
    b.push_back(420520602);
    b.push_back(872956663);
    b.push_back(643124856);
    b.push_back(53);
    b.push_back(56);
    b.push_back(20);
    b.push_back(9);
    b.push_back(68);
    b.push_back(28);
    b.push_back(83);
    b.push_back(5);
    b.push_back(669109562);
    b.push_back(989782501);
    b.push_back(436436035);
    b.push_back(62);
    b.push_back(32);
    b.push_back(83);
    b.push_back(345228555);
    b.push_back(78);
    b.push_back(57);
    b.push_back(20);
    b.push_back(47);
    b.push_back(40);
    b.push_back(76);
    b.push_back(503848911);
    b.push_back(376818690);
    b.push_back(873655122);
    b.push_back(47);
    b.push_back(401516789);
    b.push_back(97);
    b.push_back(938310901);
    b.push_back(58);
    b.push_back(14);
    b.push_back(557094501);
    b.push_back(18);
    b.push_back(23);
    b.push_back(26);
    b.push_back(89);
    b.push_back(43);
    b.push_back(66);
    b.push_back(70);
    b.push_back(65);
    b.push_back(546044502);
    b.push_back(87);
    b.push_back(33);
    b.push_back(46);
    b.push_back(811184980);
    b.push_back(501129199);
    b.push_back(21);
    b.push_back(5);
    b.push_back(47);
    b.push_back(487133410);
    b.push_back(693786981);
    b.push_back(991770911);
    b.push_back(41);
    b.push_back(62);
    b.push_back(80);
    b.push_back(41);
    b.push_back(643124856);
    b.push_back(38);
    b.push_back(874736891);
    b.push_back(640482722);
    b.push_back(87);
    b.push_back(82);
    b.push_back(96);
    b.push_back(58);
    b.push_back(18);
    b.push_back(347055772);
    b.push_back(75);
    b.push_back(59);
    b.push_back(84);
    b.push_back(43);
    b.push_back(54);
    b.push_back(76);
    b.push_back(23);
    b.push_back(857585573);
    b.push_back(95);
    b.push_back(30);
    b.push_back(80);
    b.push_back(45);
    b.push_back(18);
    b.push_back(752610784);
    b.push_back(52);
    b.push_back(433157832);
    b.push_back(12);
    b.push_back(68);
    b.push_back(49);
    b.push_back(79);
    b.push_back(589234987);
    b.push_back(853422214);
    b.push_back(548347786);
    b.push_back(340319996);
    b.push_back(560597057);
    b.push_back(937433095);
    b.push_back(32);
    b.push_back(22);
    b.push_back(97);
    b.push_back(987558875);
    b.push_back(92);
    b.push_back(550908326);
    b.push_back(497683194);
    b.push_back(3);
    b.push_back(81);
    b.push_back(915522055);
    b.push_back(752607791);
    b.push_back(651615279);
    b.push_back(41);
    b.push_back(799713548);
    b.push_back(92);
    b.push_back(54);
    b.push_back(33);
    b.push_back(32);
    b.push_back(75);
    b.push_back(57);
    b.push_back(767452426);
    b.push_back(40);
    b.push_back(782114504);
    b.push_back(89);
    b.push_back(500404448);
    b.push_back(910267988);
    b.push_back(100);
    b.push_back(919719821);
    b.push_back(719445848);
    b.push_back(600696322);
    b.push_back(511469458);
    b.push_back(75);
    b.push_back(21);
    b.push_back(500404448);
    b.push_back(66);
    b.push_back(24);
    b.push_back(569178650);
    b.push_back(38);
    b.push_back(55);
    b.push_back(534192838);
    b.push_back(29);
    b.push_back(3);
    b.push_back(74);
    b.push_back(51);
    b.push_back(24);
    b.push_back(773300700);
    b.push_back(61);
    b.push_back(515069790);
    b.push_back(60);
    b.push_back(859171275);
 }

 if (atoi(argv[1]) == 14) {
    N = 15123123;
    S = 5680852;
    T = 14818375;
    a.push_back(9563);
    a.push_back(9943);
    a.push_back(3289);
    a.push_back(8146);
    a.push_back(5648);
    a.push_back(4877);
    a.push_back(2553);
    a.push_back(5947);
    a.push_back(3384);
    a.push_back(7191);
    a.push_back(9924);
    a.push_back(5321);
    a.push_back(3552);
    a.push_back(1316);
    a.push_back(459);
    a.push_back(7800732);
    a.push_back(3538);
    a.push_back(5752);
    a.push_back(8724);
    a.push_back(1577);
    a.push_back(4902);
    a.push_back(4668);
    a.push_back(3414);
    a.push_back(7304405);
    a.push_back(191);
    a.push_back(9025);
    a.push_back(7582);
    a.push_back(9876);
    a.push_back(7647);
    a.push_back(6633);
    a.push_back(5866);
    a.push_back(8264);
    a.push_back(3377);
    a.push_back(4140);
    a.push_back(8193);
    a.push_back(11250729);
    a.push_back(574);
    a.push_back(8499);
    a.push_back(6157);
    a.push_back(11574291);
    a.push_back(10173465);
    a.push_back(10114967);
    a.push_back(3443);
    a.push_back(4776);
    a.push_back(9059);
    a.push_back(6889);
    a.push_back(5178);
    a.push_back(4876);
    a.push_back(9532);
    a.push_back(2634);
    a.push_back(4277);
    a.push_back(870);
    a.push_back(5331541);
    a.push_back(9117);
    a.push_back(3408);
    a.push_back(8284);
    a.push_back(13649239);
    a.push_back(7775);
    a.push_back(5582089);
    a.push_back(1714);
    a.push_back(2916);
    a.push_back(14858890);
    a.push_back(2204);
    a.push_back(9705);
    a.push_back(7614);
    a.push_back(11176114);
    a.push_back(980);
    a.push_back(6001);
    a.push_back(727);
    a.push_back(14000845);
    a.push_back(3817);
    a.push_back(7997);
    a.push_back(10049);
    a.push_back(5372);
    a.push_back(5067);
    a.push_back(11574291);
    a.push_back(4022);
    a.push_back(9015);
    a.push_back(7345);
    a.push_back(5154);
    a.push_back(3083);
    a.push_back(3539);
    a.push_back(5101);
    a.push_back(3170);
    a.push_back(10361579);
    a.push_back(8457);
    a.push_back(2079);
    a.push_back(9371);
    a.push_back(2541);
    a.push_back(8380);
    a.push_back(8660);
    a.push_back(1281);
    a.push_back(7887);
    a.push_back(5374);
    a.push_back(1152);
    a.push_back(2765);
    a.push_back(5809);
    a.push_back(9951);
    a.push_back(7242434);
    a.push_back(7913);
    a.push_back(5529);
    a.push_back(6295);
    a.push_back(496);
    a.push_back(6813);
    a.push_back(4132);
    a.push_back(1941);
    a.push_back(9483);
    a.push_back(10708695);
    a.push_back(8785802);
    a.push_back(639);
    a.push_back(2887);
    a.push_back(5246);
    a.push_back(5758);
    a.push_back(5507);
    a.push_back(8992);
    a.push_back(8399);
    a.push_back(1038);
    a.push_back(6561);
    a.push_back(3821);
    a.push_back(7331);
    a.push_back(52);
    a.push_back(9978);
    a.push_back(9681);
    a.push_back(7213926);
    a.push_back(2986);
    a.push_back(4933);
    a.push_back(1198);
    a.push_back(7710);
    a.push_back(6212);
    a.push_back(2642);
    a.push_back(630);
    a.push_back(4922);
    a.push_back(7303);
    a.push_back(826);
    a.push_back(5208);
    a.push_back(9992);
    a.push_back(8056);
    a.push_back(7712);
    a.push_back(8528);
    a.push_back(3536);
    a.push_back(5980);
    a.push_back(7168);
    a.push_back(6315);
    a.push_back(1096);
    a.push_back(4449);
    a.push_back(7042806);
    a.push_back(874);
    a.push_back(15025927);
    a.push_back(7172605);
    a.push_back(880);
    a.push_back(4404);
    a.push_back(2198);
    a.push_back(8785);
    a.push_back(3894);
    a.push_back(7928);
    a.push_back(12813622);
    a.push_back(6648);
    a.push_back(948);
    a.push_back(6678);
    a.push_back(8261);
    a.push_back(474);
    a.push_back(3340);
    a.push_back(5671);
    a.push_back(2826);
    a.push_back(6818);
    a.push_back(7115756);
    a.push_back(8550);
    a.push_back(9127);
    a.push_back(7989);
    a.push_back(11256565);
    a.push_back(10114967);
    a.push_back(6572611);
    a.push_back(8525);
    a.push_back(4360);
    a.push_back(2689);
    a.push_back(3767);
    a.push_back(3994);
    a.push_back(9409);
    a.push_back(5975);
    a.push_back(6101);
    a.push_back(4948);
    a.push_back(925);
    a.push_back(950);
    a.push_back(7047);
    a.push_back(7246233);
    a.push_back(7687);
    a.push_back(3389);
    a.push_back(2000);
    a.push_back(10074);
    a.push_back(7488);
    a.push_back(1232);
    a.push_back(5728);
    a.push_back(5331541);
    a.push_back(8706924);
    a.push_back(6471);
    a.push_back(5455);
    a.push_back(3176);
    a.push_back(8626);
    a.push_back(7412);
    a.push_back(9639);
    a.push_back(2044);
    a.push_back(80012);
    a.push_back(1628);
    a.push_back(9708);
    a.push_back(9163);
    a.push_back(7631);
    a.push_back(5271);
    a.push_back(483);
    a.push_back(3656);
    a.push_back(227);
    a.push_back(13434456);
    a.push_back(768);
    a.push_back(9526);
    a.push_back(5965);
    a.push_back(5323);
    a.push_back(6662);
    a.push_back(6158);
    a.push_back(7423);
    a.push_back(8938);
    a.push_back(9598);
    a.push_back(5511622);
    a.push_back(396);
    a.push_back(3526);
    a.push_back(9512);
    a.push_back(4891);
    a.push_back(6645);
    a.push_back(7705);
    a.push_back(7946);
    a.push_back(5913);
    a.push_back(86);
    a.push_back(5820);
    a.push_back(5722);
    a.push_back(4291);
    a.push_back(4171);
    a.push_back(6993);
    a.push_back(3778);
    a.push_back(9541);
    a.push_back(10079);
    a.push_back(8154);
    a.push_back(8290);
    a.push_back(3131);
    a.push_back(3071);
    a.push_back(9804);
    a.push_back(1785);
    a.push_back(3170);
    a.push_back(3125);
    a.push_back(981);
    a.push_back(6104);
    a.push_back(2213);
    a.push_back(8867);
    a.push_back(9501);
    a.push_back(7042806);
    a.push_back(7366);
    a.push_back(8107);
    a.push_back(5928);
    a.push_back(2951);
    a.push_back(3863);
    a.push_back(8087);
    a.push_back(9850);
    a.push_back(5509);
    a.push_back(8343);
    a.push_back(6301);
    a.push_back(1706);
    a.push_back(5271);
    a.push_back(6585);
    a.push_back(414);
    a.push_back(9613);
    a.push_back(7210);
    a.push_back(1151);
    a.push_back(1650);
    a.push_back(8530);
    a.push_back(9525);
    a.push_back(7934);
    a.push_back(2948);
    a.push_back(9893);
    a.push_back(2470);
    a.push_back(2118);
    a.push_back(3562);
    a.push_back(3027);
    a.push_back(7737);
    a.push_back(9925);
    a.push_back(4947);
    a.push_back(3969);
    a.push_back(2771);
    a.push_back(3844);
    a.push_back(5236);
    a.push_back(459);
    a.push_back(1338);
    a.push_back(4760);
    a.push_back(9510);
    a.push_back(879);
    a.push_back(1374);
    a.push_back(2369);
    a.push_back(12774470);
    a.push_back(313);
    a.push_back(8456);
    a.push_back(9263);
    a.push_back(1807);
    a.push_back(5562);
    a.push_back(4762);
    a.push_back(9582);
    a.push_back(8689);
    a.push_back(6728);
    a.push_back(9063);
    a.push_back(9856);
    a.push_back(8095);
    a.push_back(10101364);
    a.push_back(1615);
    a.push_back(9313);
    a.push_back(2727);
    a.push_back(5903);
    a.push_back(6367);
    a.push_back(10052);
    a.push_back(75);
    a.push_back(1111);
    a.push_back(10997788);
    a.push_back(7688);
    a.push_back(5752);
    a.push_back(115);
    a.push_back(6577);
    a.push_back(3451);
    a.push_back(8141);
    a.push_back(7277853);
    a.push_back(6572611);
    a.push_back(7062);
    a.push_back(7753);
    a.push_back(13037296);
    a.push_back(10708695);
    a.push_back(6134);
    a.push_back(7138);
    a.push_back(3254);
    a.push_back(1460);
    a.push_back(6480);
    a.push_back(6908);
    a.push_back(2251);
    a.push_back(8001);
    a.push_back(2569);
    a.push_back(5306);
    a.push_back(1831);
    a.push_back(1146);
    a.push_back(6767);
    a.push_back(3317);
    a.push_back(7394);
    a.push_back(3236);
    a.push_back(8245);
    a.push_back(3184);
    a.push_back(4819);
    a.push_back(9888);
    a.push_back(8163);
    a.push_back(2740);
    a.push_back(7451);
    a.push_back(12322601);
    a.push_back(4643);
    a.push_back(9562);
    a.push_back(3856);
    a.push_back(9101);
    a.push_back(10361579);
    a.push_back(3949);
    a.push_back(6403);
    a.push_back(3423);
    a.push_back(7043509);
    a.push_back(7425);
    a.push_back(3398);
    a.push_back(14944055);
    a.push_back(4304);
    a.push_back(1006);
    a.push_back(9529586);
    a.push_back(3392);
    a.push_back(3138);
    a.push_back(2702);
    a.push_back(5989);
    a.push_back(9084124);
    a.push_back(2295);
    a.push_back(5850);
    a.push_back(2685);
    a.push_back(157);
    a.push_back(5838);
    a.push_back(11066613);
    a.push_back(2261);
    a.push_back(58);
    a.push_back(8706924);
    a.push_back(4);
    a.push_back(5231);
    a.push_back(1522);
    a.push_back(7974);
    a.push_back(8541);
    a.push_back(246);
    a.push_back(9084124);
    a.push_back(7442);
    a.push_back(6728);
    a.push_back(9500);
    a.push_back(8224);
    a.push_back(8708);
    a.push_back(4554);
    a.push_back(6763);
    a.push_back(7056);
    a.push_back(4809);
    a.push_back(9744);
    a.push_back(2686);
    a.push_back(717);
    a.push_back(874);
    a.push_back(2088);
    a.push_back(2435);
    a.push_back(6659);
    a.push_back(8070);
    a.push_back(2961);
    a.push_back(6337);
    a.push_back(6266);
    a.push_back(2516);
    a.push_back(4381);
    a.push_back(8498);
    a.push_back(5556);
    a.push_back(6541);
    a.push_back(4390);
    a.push_back(9183);
    a.push_back(492);
    a.push_back(9176);
    a.push_back(8469);
    a.push_back(2489);
    a.push_back(6184);
    a.push_back(6295);
    a.push_back(7544);
    a.push_back(8623);
    a.push_back(14025073);
    a.push_back(9479);
    a.push_back(6734);
    a.push_back(9304);
    a.push_back(9843);
    a.push_back(3757);
    a.push_back(5990);
    a.push_back(5859);
    a.push_back(925);
    a.push_back(854);
    a.push_back(12058797);
    a.push_back(5547);
    a.push_back(7502851);
    a.push_back(6495);
    a.push_back(5511622);
    a.push_back(358);
    a.push_back(12461685);
    a.push_back(4182);
    a.push_back(12774470);
    a.push_back(3948);
    a.push_back(6588);
    a.push_back(9197679);
    a.push_back(6502479);
    a.push_back(7758);
    a.push_back(8291);
    a.push_back(4910);
    a.push_back(4040);
    a.push_back(3611);
    a.push_back(14765738);
    a.push_back(1547);
    a.push_back(6923);
    a.push_back(12176164);
    a.push_back(152);
    a.push_back(8617);
    a.push_back(12924654);
    a.push_back(6052301);
    a.push_back(7405488);
    a.push_back(2403);
    a.push_back(1388);
    b.push_back(1871);
    b.push_back(4214);
    b.push_back(1853);
    b.push_back(628);
    b.push_back(121);
    b.push_back(3913);
    b.push_back(8654);
    b.push_back(1448);
    b.push_back(2994);
    b.push_back(9461);
    b.push_back(9941);
    b.push_back(2390);
    b.push_back(4536);
    b.push_back(8878);
    b.push_back(5996);
    b.push_back(12461685);
    b.push_back(9033);
    b.push_back(1182);
    b.push_back(8292);
    b.push_back(4711);
    b.push_back(5116);
    b.push_back(3300);
    b.push_back(9778);
    b.push_back(12924654);
    b.push_back(399);
    b.push_back(1528);
    b.push_back(8662);
    b.push_back(7983);
    b.push_back(5465);
    b.push_back(3887);
    b.push_back(1011);
    b.push_back(7793);
    b.push_back(569);
    b.push_back(176);
    b.push_back(3818);
    b.push_back(7405488);
    b.push_back(960);
    b.push_back(7081);
    b.push_back(2099);
    b.push_back(11256565);
    b.push_back(7242434);
    b.push_back(11250729);
    b.push_back(8589);
    b.push_back(5671);
    b.push_back(3462);
    b.push_back(6731);
    b.push_back(840);
    b.push_back(1894);
    b.push_back(6701);
    b.push_back(3444);
    b.push_back(9136);
    b.push_back(165);
    b.push_back(11256565);
    b.push_back(6745);
    b.push_back(8799);
    b.push_back(7738);
    b.push_back(6572611);
    b.push_back(5981);
    b.push_back(7213926);
    b.push_back(9015);
    b.push_back(2069);
    b.push_back(12774470);
    b.push_back(6760);
    b.push_back(5599);
    b.push_back(6988);
    b.push_back(5331541);
    b.push_back(7380);
    b.push_back(8365);
    b.push_back(2612);
    b.push_back(11250729);
    b.push_back(1108);
    b.push_back(609);
    b.push_back(7236);
    b.push_back(7605);
    b.push_back(1606);
    b.push_back(7304405);
    b.push_back(4168);
    b.push_back(5664);
    b.push_back(1382);
    b.push_back(8533);
    b.push_back(5328);
    b.push_back(2636);
    b.push_back(6797);
    b.push_back(9020);
    b.push_back(5331541);
    b.push_back(975);
    b.push_back(621);
    b.push_back(9733);
    b.push_back(4212);
    b.push_back(1879);
    b.push_back(1436);
    b.push_back(2564);
    b.push_back(9156);
    b.push_back(2589);
    b.push_back(6246);
    b.push_back(3566);
    b.push_back(5325);
    b.push_back(1122);
    b.push_back(12058797);
    b.push_back(5088);
    b.push_back(3072);
    b.push_back(6154);
    b.push_back(8062);
    b.push_back(5171);
    b.push_back(5697);
    b.push_back(9912);
    b.push_back(5268);
    b.push_back(13037296);
    b.push_back(14765738);
    b.push_back(266);
    b.push_back(1151);
    b.push_back(3632);
    b.push_back(5747);
    b.push_back(2961);
    b.push_back(3550);
    b.push_back(4911);
    b.push_back(2694);
    b.push_back(5635);
    b.push_back(1685);
    b.push_back(6095);
    b.push_back(40);
    b.push_back(5554);
    b.push_back(7281);
    b.push_back(7043509);
    b.push_back(8701);
    b.push_back(973);
    b.push_back(9057);
    b.push_back(9660);
    b.push_back(7532);
    b.push_back(6809);
    b.push_back(5948);
    b.push_back(6165);
    b.push_back(6827);
    b.push_back(5736);
    b.push_back(2764);
    b.push_back(1487);
    b.push_back(4014);
    b.push_back(7619);
    b.push_back(2508);
    b.push_back(6086);
    b.push_back(9300);
    b.push_back(7539);
    b.push_back(2076);
    b.push_back(1180);
    b.push_back(6781);
    b.push_back(7172605);
    b.push_back(8782);
    b.push_back(9529586);
    b.push_back(14025073);
    b.push_back(8648);
    b.push_back(2649);
    b.push_back(7465);
    b.push_back(6713);
    b.push_back(9806);
    b.push_back(9672);
    b.push_back(7115756);
    b.push_back(616);
    b.push_back(2359);
    b.push_back(5684);
    b.push_back(1743);
    b.push_back(3745);
    b.push_back(484);
    b.push_back(394);
    b.push_back(8154);
    b.push_back(1063);
    b.push_back(10114967);
    b.push_back(9752);
    b.push_back(9897);
    b.push_back(3400);
    b.push_back(11066613);
    b.push_back(14000845);
    b.push_back(7242434);
    b.push_back(1933);
    b.push_back(3188);
    b.push_back(2695);
    b.push_back(9865);
    b.push_back(6333);
    b.push_back(3369);
    b.push_back(1305);
    b.push_back(3961);
    b.push_back(7345);
    b.push_back(7800);
    b.push_back(9316);
    b.push_back(6953);
    b.push_back(14944055);
    b.push_back(5773);
    b.push_back(4582);
    b.push_back(7191);
    b.push_back(1867);
    b.push_back(10036);
    b.push_back(8332);
    b.push_back(1088);
    b.push_back(5511622);
    b.push_back(10101364);
    b.push_back(4122);
    b.push_back(4791);
    b.push_back(8865);
    b.push_back(5721);
    b.push_back(8197);
    b.push_back(9720);
    b.push_back(4737);
    b.push_back(10997788);
    b.push_back(1872);
    b.push_back(6641);
    b.push_back(5243);
    b.push_back(3897);
    b.push_back(465);
    b.push_back(6813);
    b.push_back(8611);
    b.push_back(4660);
    b.push_back(15025927);
    b.push_back(7753);
    b.push_back(247);
    b.push_back(3115);
    b.push_back(5921);
    b.push_back(4614);
    b.push_back(7503);
    b.push_back(5218);
    b.push_back(3210);
    b.push_back(1900);
    b.push_back(11574291);
    b.push_back(7754);
    b.push_back(3447);
    b.push_back(5461);
    b.push_back(5007);
    b.push_back(8015);
    b.push_back(8594);
    b.push_back(6172);
    b.push_back(7692);
    b.push_back(6763);
    b.push_back(8697);
    b.push_back(9613);
    b.push_back(5637);
    b.push_back(5772);
    b.push_back(3590);
    b.push_back(3742);
    b.push_back(6790);
    b.push_back(5289);
    b.push_back(123);
    b.push_back(5190);
    b.push_back(7543);
    b.push_back(7201);
    b.push_back(7272);
    b.push_back(5456);
    b.push_back(575);
    b.push_back(2942);
    b.push_back(10);
    b.push_back(3405);
    b.push_back(1974);
    b.push_back(7173);
    b.push_back(3785);
    b.push_back(12176164);
    b.push_back(153);
    b.push_back(2166);
    b.push_back(6006);
    b.push_back(1561);
    b.push_back(4586);
    b.push_back(7967);
    b.push_back(146);
    b.push_back(2821);
    b.push_back(8590);
    b.push_back(964);
    b.push_back(1836);
    b.push_back(7944);
    b.push_back(5058);
    b.push_back(7034);
    b.push_back(2108);
    b.push_back(796);
    b.push_back(7949);
    b.push_back(7943);
    b.push_back(4517);
    b.push_back(1303);
    b.push_back(1848);
    b.push_back(9392);
    b.push_back(2074);
    b.push_back(2837);
    b.push_back(7902);
    b.push_back(1361);
    b.push_back(798);
    b.push_back(4228);
    b.push_back(9669);
    b.push_back(8008);
    b.push_back(9922);
    b.push_back(6532);
    b.push_back(4817);
    b.push_back(6455);
    b.push_back(1264);
    b.push_back(9950);
    b.push_back(5546);
    b.push_back(7617);
    b.push_back(1590);
    b.push_back(4571);
    b.push_back(1622);
    b.push_back(5582089);
    b.push_back(269);
    b.push_back(6302);
    b.push_back(2678);
    b.push_back(2864);
    b.push_back(266);
    b.push_back(6477);
    b.push_back(2583);
    b.push_back(7408);
    b.push_back(737);
    b.push_back(2535);
    b.push_back(4884);
    b.push_back(9260);
    b.push_back(12813622);
    b.push_back(4451);
    b.push_back(6230);
    b.push_back(7120);
    b.push_back(4189);
    b.push_back(4476);
    b.push_back(7961);
    b.push_back(2597);
    b.push_back(1800);
    b.push_back(7502851);
    b.push_back(5846);
    b.push_back(9726);
    b.push_back(4078);
    b.push_back(1895);
    b.push_back(5973);
    b.push_back(8439);
    b.push_back(13649239);
    b.push_back(10173465);
    b.push_back(3043);
    b.push_back(71);
    b.push_back(13434456);
    b.push_back(13434456);
    b.push_back(3687);
    b.push_back(6033);
    b.push_back(5747);
    b.push_back(2961);
    b.push_back(4414);
    b.push_back(3880);
    b.push_back(8809);
    b.push_back(8812);
    b.push_back(9205);
    b.push_back(1281);
    b.push_back(9484);
    b.push_back(7253);
    b.push_back(3737);
    b.push_back(5825);
    b.push_back(9660);
    b.push_back(909);
    b.push_back(2235);
    b.push_back(4052);
    b.push_back(2617);
    b.push_back(2348);
    b.push_back(8589);
    b.push_back(7130);
    b.push_back(1253);
    b.push_back(7800732);
    b.push_back(6214);
    b.push_back(1839);
    b.push_back(7810);
    b.push_back(5093);
    b.push_back(11176114);
    b.push_back(9684);
    b.push_back(6526);
    b.push_back(6640);
    b.push_back(8785802);
    b.push_back(4148);
    b.push_back(8871);
    b.push_back(10708695);
    b.push_back(710);
    b.push_back(5875);
    b.push_back(14858890);
    b.push_back(10057);
    b.push_back(1083);
    b.push_back(2853);
    b.push_back(902);
    b.push_back(10101364);
    b.push_back(6895);
    b.push_back(5359);
    b.push_back(2465);
    b.push_back(1107);
    b.push_back(8760);
    b.push_back(7304405);
    b.push_back(5190);
    b.push_back(2844);
    b.push_back(9084124);
    b.push_back(2011);
    b.push_back(4067);
    b.push_back(3818);
    b.push_back(8773);
    b.push_back(6853);
    b.push_back(9501);
    b.push_back(12813622);
    b.push_back(1912);
    b.push_back(9058);
    b.push_back(1586);
    b.push_back(5083);
    b.push_back(7390);
    b.push_back(5817);
    b.push_back(8841);
    b.push_back(6962);
    b.push_back(8308);
    b.push_back(3344);
    b.push_back(9932);
    b.push_back(6813);
    b.push_back(4842);
    b.push_back(4689);
    b.push_back(1105);
    b.push_back(3450);
    b.push_back(1607);
    b.push_back(7739);
    b.push_back(9847);
    b.push_back(1850);
    b.push_back(3783);
    b.push_back(2327);
    b.push_back(9745);
    b.push_back(5031);
    b.push_back(6244);
    b.push_back(1053);
    b.push_back(736);
    b.push_back(5967);
    b.push_back(8100);
    b.push_back(5922);
    b.push_back(3834);
    b.push_back(2694);
    b.push_back(8865);
    b.push_back(3083);
    b.push_back(4193);
    b.push_back(6052301);
    b.push_back(1816);
    b.push_back(5703);
    b.push_back(1855);
    b.push_back(3005);
    b.push_back(6168);
    b.push_back(7091);
    b.push_back(7021);
    b.push_back(2474);
    b.push_back(6117);
    b.push_back(12322601);
    b.push_back(1755);
    b.push_back(8706924);
    b.push_back(1747);
    b.push_back(11256565);
    b.push_back(420);
    b.push_back(53885);
    b.push_back(3241);
    b.push_back(7213926);
    b.push_back(4215);
    b.push_back(782);
    b.push_back(7246233);
    b.push_back(10361579);
    b.push_back(8060);
    b.push_back(6139);
    b.push_back(2052);
    b.push_back(7595);
    b.push_back(6094);
    b.push_back(7042806);
    b.push_back(1978);
    b.push_back(8291);
    b.push_back(7172605);
    b.push_back(2117);
    b.push_back(4449);
    b.push_back(7277853);
    b.push_back(6502479);
    b.push_back(9197679);
    b.push_back(877);
    b.push_back(6169);
 }

 if (atoi(argv[1]) == 17) {
    N = 1000000000;
    S = 84751923;
    T = 258320530;
    a.push_back(885580797);
    a.push_back(4811755);
    a.push_back(76943306);
    a.push_back(721433898);
    a.push_back(935084960);
    a.push_back(725860391);
    a.push_back(803149106);
    a.push_back(937400155);
    a.push_back(784508451);
    a.push_back(27063802);
    a.push_back(987260727);
    a.push_back(838588160);
    a.push_back(741726881);
    a.push_back(794965620);
    a.push_back(538857779);
    a.push_back(873865155);
    a.push_back(69576948);
    a.push_back(947638135);
    a.push_back(509241708);
    a.push_back(9423378);
    a.push_back(721003974);
    a.push_back(905609635);
    a.push_back(3613885);
    a.push_back(350842791);
    a.push_back(772907176);
    a.push_back(477830091);
    a.push_back(410794772);
    a.push_back(84751923);
    a.push_back(33097689);
    a.push_back(381466395);
    a.push_back(60297236);
    a.push_back(28716126);
    a.push_back(896337930);
    a.push_back(52928142);
    a.push_back(570484145);
    a.push_back(409002962);
    a.push_back(685165094);
    a.push_back(95144892);
    a.push_back(537374147);
    a.push_back(625669688);
    a.push_back(588292475);
    a.push_back(681332438);
    a.push_back(860749084);
    a.push_back(753321035);
    a.push_back(981350184);
    a.push_back(784508451);
    a.push_back(52994947);
    a.push_back(489176751);
    a.push_back(24199424);
    a.push_back(447856570);
    a.push_back(88895714);
    a.push_back(914625942);
    a.push_back(850569794);
    a.push_back(56520770);
    a.push_back(911421331);
    a.push_back(893556569);
    a.push_back(395062020);
    a.push_back(42978277);
    a.push_back(424215581);
    a.push_back(4882405);
    a.push_back(15614793);
    a.push_back(350842791);
    a.push_back(4801493);
    a.push_back(746909652);
    a.push_back(53802534);
    a.push_back(991050377);
    a.push_back(861301504);
    a.push_back(873735323);
    a.push_back(884201274);
    a.push_back(981350184);
    a.push_back(565133272);
    a.push_back(621499934);
    a.push_back(981039082);
    a.push_back(622576062);
    a.push_back(438384234);
    a.push_back(38335973);
    a.push_back(485502094);
    a.push_back(364190245);
    a.push_back(23967768);
    a.push_back(394373068);
    a.push_back(591046743);
    a.push_back(856447201);
    a.push_back(796397119);
    a.push_back(20490050);
    a.push_back(85793843);
    a.push_back(435526723);
    a.push_back(489176751);
    a.push_back(698321178);
    a.push_back(22162336);
    a.push_back(628333797);
    a.push_back(964756750);
    a.push_back(20214630);
    a.push_back(89627168);
    a.push_back(33866757);
    a.push_back(883761176);
    a.push_back(50386268);
    a.push_back(34245447);
    a.push_back(622740886);
    a.push_back(485502094);
    a.push_back(820401276);
    a.push_back(695345369);
    a.push_back(685165094);
    a.push_back(24579328);
    a.push_back(10463220);
    a.push_back(776988628);
    a.push_back(372768014);
    a.push_back(395062020);
    a.push_back(18166492);
    a.push_back(671861183);
    a.push_back(856799924);
    a.push_back(622740886);
    a.push_back(42732895);
    a.push_back(177286);
    a.push_back(982080376);
    a.push_back(409002962);
    a.push_back(447856570);
    a.push_back(936142481);
    a.push_back(42175392);
    a.push_back(3677617);
    a.push_back(865361060);
    a.push_back(505022526);
    a.push_back(44337766);
    a.push_back(50983331);
    a.push_back(697635308);
    a.push_back(742679379);
    a.push_back(770319382);
    a.push_back(59886402);
    a.push_back(671861183);
    a.push_back(674572606);
    a.push_back(400894789);
    a.push_back(492245792);
    a.push_back(988074723);
    a.push_back(727093074);
    a.push_back(469715831);
    a.push_back(56699181);
    a.push_back(903536974);
    a.push_back(48131397);
    a.push_back(579147196);
    a.push_back(671438514);
    a.push_back(24916295);
    a.push_back(865361060);
    a.push_back(886471889);
    a.push_back(29970266);
    a.push_back(779430615);
    a.push_back(460826871);
    a.push_back(31436821);
    a.push_back(880049703);
    a.push_back(961798376);
    a.push_back(15799962);
    a.push_back(419805047);
    a.push_back(911421331);
    a.push_back(61450369);
    a.push_back(712527661);
    a.push_back(911421331);
    a.push_back(771215068);
    a.push_back(883761176);
    a.push_back(46327718);
    a.push_back(859400291);
    a.push_back(738750783);
    a.push_back(721433898);
    a.push_back(884201274);
    a.push_back(48396002);
    a.push_back(857294929);
    a.push_back(479056226);
    a.push_back(845580656);
    a.push_back(589145889);
    a.push_back(49759796);
    a.push_back(68040756);
    a.push_back(796433178);
    a.push_back(995130584);
    a.push_back(687639089);
    a.push_back(350842791);
    a.push_back(916999801);
    a.push_back(538857779);
    a.push_back(384630692);
    a.push_back(72766122);
    a.push_back(455265721);
    a.push_back(746909652);
    a.push_back(424215581);
    a.push_back(881387687);
    a.push_back(409002962);
    a.push_back(74227869);
    a.push_back(438384234);
    a.push_back(622723740);
    a.push_back(721433898);
    a.push_back(30687919);
    a.push_back(372368828);
    a.push_back(26526895);
    a.push_back(3902083);
    a.push_back(56106502);
    a.push_back(622723740);
    a.push_back(964756750);
    a.push_back(7728746);
    a.push_back(56295466);
    a.push_back(780464520);
    a.push_back(518854867);
    a.push_back(61990941);
    a.push_back(26250532);
    a.push_back(817179298);
    a.push_back(51217179);
    a.push_back(362091287);
    a.push_back(517704969);
    a.push_back(57691477);
    a.push_back(978719300);
    a.push_back(857175144);
    a.push_back(558968887);
    a.push_back(498234351);
    a.push_back(423615995);
    a.push_back(42399129);
    a.push_back(698321178);
    a.push_back(738750783);
    a.push_back(85741866);
    a.push_back(806194488);
    a.push_back(395062020);
    a.push_back(865361060);
    a.push_back(772907176);
    a.push_back(742570048);
    a.push_back(27200482);
    a.push_back(849747076);
    a.push_back(52159264);
    a.push_back(856447201);
    a.push_back(396746401);
    a.push_back(445294577);
    a.push_back(961798376);
    a.push_back(413416034);
    a.push_back(563223129);
    a.push_back(591026795);
    a.push_back(796777415);
    a.push_back(5649070);
    a.push_back(1610258);
    a.push_back(727304850);
    a.push_back(695345369);
    a.push_back(60664684);
    a.push_back(881387687);
    a.push_back(423865246);
    a.push_back(808314528);
    a.push_back(23200252);
    a.push_back(516449376);
    a.push_back(71923455);
    a.push_back(591026795);
    a.push_back(17382080);
    a.push_back(671438514);
    a.push_back(638336403);
    a.push_back(39613345);
    a.push_back(419805047);
    a.push_back(803149106);
    a.push_back(396746401);
    a.push_back(46861080);
    a.push_back(14338260);
    a.push_back(29264340);
    a.push_back(449379757);
    a.push_back(42986408);
    a.push_back(685344751);
    a.push_back(873865155);
    a.push_back(805674678);
    a.push_back(58931875);
    a.push_back(671438514);
    a.push_back(755938219);
    a.push_back(916999801);
    a.push_back(31483144);
    a.push_back(973401019);
    a.push_back(687639089);
    a.push_back(982080376);
    a.push_back(419805047);
    a.push_back(674572606);
    a.push_back(885580797);
    a.push_back(845580656);
    a.push_back(479056226);
    a.push_back(861495164);
    a.push_back(675620103);
    a.push_back(916999801);
    a.push_back(56586853);
    a.push_back(364190245);
    a.push_back(347247766);
    a.push_back(806194488);
    a.push_back(399274449);
    a.push_back(919910724);
    a.push_back(24325029);
    a.push_back(50376136);
    a.push_back(32734556);
    a.push_back(780464520);
    a.push_back(884201274);
    a.push_back(75897055);
    a.push_back(796069945);
    a.push_back(591046743);
    a.push_back(21890295);
    a.push_back(11278917);
    a.push_back(776988628);
    a.push_back(469715831);
    a.push_back(680612445);
    a.push_back(400642807);
    a.push_back(799623900);
    a.push_back(671438514);
    a.push_back(350154812);
    a.push_back(438384234);
    a.push_back(73850943);
    a.push_back(973051508);
    a.push_back(725860391);
    a.push_back(39299990);
    a.push_back(582150820);
    a.push_back(438384234);
    a.push_back(903865336);
    a.push_back(536537731);
    a.push_back(557039890);
    a.push_back(57737848);
    a.push_back(52541914);
    a.push_back(622740886);
    a.push_back(881387687);
    a.push_back(445423076);
    a.push_back(563223129);
    a.push_back(34737358);
    a.push_back(771215068);
    a.push_back(423615995);
    a.push_back(971711);
    a.push_back(591046743);
    a.push_back(15553575);
    a.push_back(961798376);
    a.push_back(529362631);
    a.push_back(861301504);
    a.push_back(613077155);
    a.push_back(870348124);
    a.push_back(567709375);
    a.push_back(746909652);
    a.push_back(765747960);
    a.push_back(6311467);
    a.push_back(685165094);
    a.push_back(936887987);
    a.push_back(712527661);
    a.push_back(49178813);
    a.push_back(489176751);
    a.push_back(15026263);
    a.push_back(739981);
    a.push_back(28641577);
    a.push_back(546807743);
    a.push_back(803149106);
    a.push_back(678785941);
    a.push_back(613077155);
    a.push_back(675620103);
    a.push_back(65225300);
    a.push_back(973401019);
    a.push_back(419805047);
    a.push_back(935084960);
    a.push_back(6111409);
    a.push_back(615367605);
    a.push_back(671861183);
    a.push_back(721003974);
    a.push_back(973051508);
    a.push_back(97805515);
    a.push_back(712527661);
    a.push_back(479056226);
    a.push_back(395109129);
    a.push_back(414362404);
    a.push_back(54454634);
    a.push_back(766784140);
    a.push_back(87021772);
    a.push_back(797148018);
    a.push_back(591046743);
    a.push_back(396746401);
    a.push_back(937400155);
    a.push_back(771215068);
    a.push_back(38958042);
    a.push_back(447856570);
    a.push_back(934188508);
    a.push_back(27302463);
    a.push_back(567709375);
    a.push_back(349413523);
    a.push_back(898391138);
    a.push_back(727093074);
    a.push_back(55422665);
    a.push_back(685165094);
    a.push_back(591026795);
    a.push_back(42029665);
    a.push_back(25964986);
    a.push_back(674572606);
    a.push_back(80193943);
    a.push_back(763231922);
    a.push_back(671438514);
    a.push_back(838588160);
    a.push_back(964756750);
    a.push_back(45745174);
    a.push_back(22744765);
    a.push_back(766784140);
    a.push_back(372368828);
    a.push_back(4544251);
    a.push_back(796069945);
    a.push_back(492245792);
    a.push_back(76575270);
    a.push_back(37864332);
    a.push_back(991746900);
    a.push_back(680612445);
    a.push_back(981039082);
    a.push_back(975726570);
    a.push_back(372368828);
    a.push_back(621499934);
    a.push_back(622740886);
    a.push_back(26270068);
    a.push_back(395062020);
    a.push_back(69221);
    a.push_back(43220458);
    a.push_back(725860391);
    a.push_back(618729668);
    a.push_back(350154812);
    a.push_back(896337930);
    a.push_back(981350184);
    a.push_back(628333797);
    a.push_back(1320976);
    a.push_back(707961719);
    a.push_back(780464520);
    a.push_back(541495681);
    a.push_back(6436492);
    a.push_back(423865246);
    a.push_back(399274449);
    a.push_back(5884682);
    a.push_back(873865155);
    a.push_back(455265721);
    a.push_back(479056226);
    a.push_back(968377466);
    a.push_back(685344751);
    a.push_back(68493582);
    a.push_back(638336403);
    a.push_back(881387687);
    a.push_back(409002962);
    a.push_back(466295582);
    a.push_back(589145889);
    a.push_back(712527661);
    a.push_back(14680443);
    a.push_back(695345369);
    a.push_back(410794772);
    a.push_back(991050377);
    a.push_back(400642807);
    a.push_back(68349767);
    a.push_back(861495164);
    a.push_back(460306689);
    a.push_back(413416034);
    a.push_back(656451533);
    a.push_back(727304850);
    a.push_back(381466395);
    a.push_back(31262791);
    a.push_back(81604398);
    a.push_back(460826871);
    a.push_back(772907176);
    a.push_back(725860391);
    a.push_back(1116598);
    a.push_back(968377466);
    a.push_back(936887987);
    a.push_back(419256703);
    a.push_back(58951805);
    a.push_back(727304850);
    a.push_back(674572606);
    a.push_back(907321836);
    a.push_back(789082413);
    a.push_back(987260727);
    a.push_back(991050377);
    a.push_back(995130584);
    a.push_back(985293433);
    a.push_back(529362631);
    a.push_back(395109129);
    a.push_back(794965620);
    a.push_back(2933151);
    a.push_back(516449376);
    a.push_back(656451533);
    a.push_back(780305962);
    a.push_back(557039890);
    a.push_back(74255150);
    a.push_back(799468873);
    a.push_back(964756750);
    a.push_back(71929130);
    a.push_back(896337930);
    a.push_back(856799924);
    a.push_back(445423076);
    a.push_back(927603231);
    a.push_back(784508451);
    a.push_back(50176045);
    a.push_back(738750783);
    a.push_back(57964313);
    a.push_back(8822428);
    a.push_back(48347992);
    a.push_back(27060101);
    a.push_back(505022526);
    a.push_back(577200303);
    a.push_back(498610185);
    a.push_back(1248855);
    a.push_back(873735323);
    a.push_back(898391138);
    a.push_back(964756750);
    a.push_back(23158511);
    a.push_back(460826871);
    a.push_back(893556569);
    a.push_back(780305962);
    a.push_back(622740886);
    a.push_back(6023024);
    a.push_back(397564340);
    a.push_back(438384234);
    a.push_back(755622762);
    a.push_back(905609635);
    a.push_back(29543887);
    a.push_back(799468873);
    a.push_back(551749682);
    a.push_back(913320830);
    a.push_back(885580797);
    a.push_back(865361060);
    a.push_back(61080305);
    a.push_back(857294929);
    a.push_back(880049703);
    a.push_back(893680204);
    a.push_back(861495164);
    a.push_back(898391138);
    a.push_back(423865246);
    a.push_back(957439114);
    a.push_back(981039082);
    a.push_back(67251931);
    a.push_back(394373068);
    a.push_back(687639089);
    a.push_back(675620103);
    a.push_back(477830091);
    a.push_back(395062020);
    a.push_back(82179775);
    a.push_back(40458084);
    a.push_back(70962597);
    a.push_back(819271825);
    a.push_back(659941706);
    a.push_back(67179537);
    a.push_back(799623900);
    a.push_back(817179298);
    a.push_back(771215068);
    a.push_back(632357111);
    a.push_back(776988628);
    a.push_back(498610185);
    a.push_back(857294929);
    a.push_back(432796372);
    a.push_back(868062849);
    a.push_back(529362631);
    a.push_back(885580797);
    a.push_back(765747960);
    a.push_back(27921644);
    a.push_back(674572606);
    a.push_back(763231922);
    a.push_back(991050377);
    a.push_back(806194488);
    a.push_back(682131142);
    a.push_back(861301504);
    a.push_back(48198618);
    a.push_back(859400291);
    a.push_back(591046743);
    a.push_back(546807743);
    a.push_back(907321836);
    a.push_back(29352383);
    b.push_back(347247766);
    b.push_back(445294577);
    b.push_back(349413523);
    b.push_back(947638135);
    b.push_back(14776376);
    b.push_back(23453482);
    b.push_back(19924252);
    b.push_back(622576062);
    b.push_back(41886388);
    b.push_back(861495164);
    b.push_back(772907176);
    b.push_back(978719300);
    b.push_back(551749682);
    b.push_back(678785941);
    b.push_back(565133272);
    b.push_back(51590226);
    b.push_back(981039082);
    b.push_back(766784140);
    b.push_back(856799924);
    b.push_back(477830091);
    b.push_back(937400155);
    b.push_back(796433178);
    b.push_back(885580797);
    b.push_back(622723740);
    b.push_back(628333797);
    b.push_back(71009650);
    b.push_back(96401000);
    b.push_back(671438514);
    b.push_back(780305962);
    b.push_back(529362631);
    b.push_back(570484145);
    b.push_back(873735323);
    b.push_back(659941706);
    b.push_back(509241708);
    b.push_back(632357111);
    b.push_back(58056234);
    b.push_back(49608333);
    b.push_back(799623900);
    b.push_back(850569794);
    b.push_back(447856570);
    b.push_back(681332438);
    b.push_back(937400155);
    b.push_back(885580797);
    b.push_back(23529885);
    b.push_back(73074202);
    b.push_back(4578069);
    b.push_back(466295582);
    b.push_back(911421331);
    b.push_back(893556569);
    b.push_back(5323527);
    b.push_back(588292475);
    b.push_back(557039890);
    b.push_back(987260727);
    b.push_back(861495164);
    b.push_back(868062849);
    b.push_back(975726570);
    b.push_back(746909652);
    b.push_back(414362404);
    b.push_back(40602720);
    b.push_back(988074723);
    b.push_back(865361060);
    b.push_back(618729668);
    b.push_back(766784140);
    b.push_back(85911578);
    b.push_back(905609635);
    b.push_back(763231922);
    b.push_back(591046743);
    b.push_back(17279311);
    b.push_back(538857779);
    b.push_back(893680204);
    b.push_back(445423076);
    b.push_back(47089727);
    b.push_back(2964579);
    b.push_back(985293433);
    b.push_back(5648207);
    b.push_back(991746900);
    b.push_back(64583193);
    b.push_back(808314528);
    b.push_back(796777415);
    b.push_back(936142481);
    b.push_back(74822765);
    b.push_back(914625942);
    b.push_back(675620103);
    b.push_back(685344751);
    b.push_back(563223129);
    b.push_back(794965620);
    b.push_back(46967901);
    b.push_back(414362404);
    b.push_back(414362404);
    b.push_back(857175144);
    b.push_back(845580656);
    b.push_back(565133272);
    b.push_back(991746900);
    b.push_back(968377466);
    b.push_back(674572606);
    b.push_back(927603231);
    b.push_back(803149106);
    b.push_back(28464406);
    b.push_back(687639089);
    b.push_back(541495681);
    b.push_back(68172340);
    b.push_back(35321223);
    b.push_back(995130584);
    b.push_back(445294577);
    b.push_back(362091287);
    b.push_back(770319382);
    b.push_back(58799182);
    b.push_back(632357111);
    b.push_back(35661612);
    b.push_back(721003974);
    b.push_back(517704969);
    b.push_back(799468873);
    b.push_back(884201274);
    b.push_back(384630692);
    b.push_back(883761176);
    b.push_back(65995411);
    b.push_back(698321178);
    b.push_back(988074723);
    b.push_back(797148018);
    b.push_back(460306689);
    b.push_back(74659291);
    b.push_back(413416034);
    b.push_back(460826871);
    b.push_back(399274449);
    b.push_back(25832053);
    b.push_back(935084960);
    b.push_back(498610185);
    b.push_back(968377466);
    b.push_back(17585079);
    b.push_back(873865155);
    b.push_back(927603231);
    b.push_back(674572606);
    b.push_back(87785056);
    b.push_back(886471889);
    b.push_back(808314528);
    b.push_back(857294929);
    b.push_back(919910724);
    b.push_back(903865336);
    b.push_back(796069945);
    b.push_back(409002962);
    b.push_back(34846378);
    b.push_back(423615995);
    b.push_back(350842791);
    b.push_back(349413523);
    b.push_back(37284885);
    b.push_back(780464520);
    b.push_back(973401019);
    b.push_back(776988628);
    b.push_back(489176751);
    b.push_back(34195009);
    b.push_back(61149860);
    b.push_back(577200303);
    b.push_back(582150820);
    b.push_back(56656606);
    b.push_back(82532527);
    b.push_back(988074723);
    b.push_back(817179298);
    b.push_back(432796372);
    b.push_back(43158364);
    b.push_back(2824280);
    b.push_back(91637773);
    b.push_back(985293433);
    b.push_back(898391138);
    b.push_back(400642807);
    b.push_back(26556506);
    b.push_back(423865246);
    b.push_back(659941706);
    b.push_back(682131142);
    b.push_back(671861183);
    b.push_back(516449376);
    b.push_back(460826871);
    b.push_back(8412731);
    b.push_back(29537743);
    b.push_back(7431755);
    b.push_back(419805047);
    b.push_back(489176751);
    b.push_back(622740886);
    b.push_back(741051);
    b.push_back(991746900);
    b.push_back(395062020);
    b.push_back(20600308);
    b.push_back(755938219);
    b.push_back(15277647);
    b.push_back(995130584);
    b.push_back(59270889);
    b.push_back(861301504);
    b.push_back(988074723);
    b.push_back(536537731);
    b.push_back(927603231);
    b.push_back(384630692);
    b.push_back(516449376);
    b.push_back(26230657);
    b.push_back(396746401);
    b.push_back(638336403);
    b.push_back(622723740);
    b.push_back(394373068);
    b.push_back(845580656);
    b.push_back(973051508);
    b.push_back(870348124);
    b.push_back(865361060);
    b.push_back(893556569);
    b.push_back(819271825);
    b.push_back(541495681);
    b.push_back(492245792);
    b.push_back(350842791);
    b.push_back(919910724);
    b.push_back(738750783);
    b.push_back(87158268);
    b.push_back(362091287);
    b.push_back(33840376);
    b.push_back(881387687);
    b.push_back(766784140);
    b.push_back(52438231);
    b.push_back(59060283);
    b.push_back(24992301);
    b.push_back(24816663);
    b.push_back(409002962);
    b.push_back(873865155);
    b.push_back(884201274);
    b.push_back(903536974);
    b.push_back(419256703);
    b.push_back(44122089);
    b.push_back(914625942);
    b.push_back(39701412);
    b.push_back(13088058);
    b.push_back(903536974);
    b.push_back(349413523);
    b.push_back(591026795);
    b.push_back(746909652);
    b.push_back(936142481);
    b.push_back(46955022);
    b.push_back(577200303);
    b.push_back(797148018);
    b.push_back(42664059);
    b.push_back(936887987);
    b.push_back(755622762);
    b.push_back(780464520);
    b.push_back(350154812);
    b.push_back(789082413);
    b.push_back(65932261);
    b.push_back(766784140);
    b.push_back(60771241);
    b.push_back(536537731);
    b.push_back(618729668);
    b.push_back(916999801);
    b.push_back(934188508);
    b.push_back(819271825);
    b.push_back(517704969);
    b.push_back(819271825);
    b.push_back(505022526);
    b.push_back(982080376);
    b.push_back(591046743);
    b.push_back(10374929);
    b.push_back(1946594);
    b.push_back(796397119);
    b.push_back(885580797);
    b.push_back(964756750);
    b.push_back(712527661);
    b.push_back(796777415);
    b.push_back(789082413);
    b.push_back(2857942);
    b.push_back(880049703);
    b.push_back(419805047);
    b.push_back(66092936);
    b.push_back(41723945);
    b.push_back(28196530);
    b.push_back(753321035);
    b.push_back(424215581);
    b.push_back(707961719);
    b.push_back(742570048);
    b.push_back(40348319);
    b.push_back(394373068);
    b.push_back(30586039);
    b.push_back(727093074);
    b.push_back(38113647);
    b.push_back(16807562);
    b.push_back(413416034);
    b.push_back(981039082);
    b.push_back(536537731);
    b.push_back(632357111);
    b.push_back(57503472);
    b.push_back(39904292);
    b.push_back(727093074);
    b.push_back(845580656);
    b.push_back(47372043);
    b.push_back(973401019);
    b.push_back(424215581);
    b.push_back(975726570);
    b.push_back(26921735);
    b.push_back(372368828);
    b.push_back(435526723);
    b.push_back(868062849);
    b.push_back(32212995);
    b.push_back(820401276);
    b.push_back(15962062);
    b.push_back(529362631);
    b.push_back(47940972);
    b.push_back(48012243);
    b.push_back(622740886);
    b.push_back(505022526);
    b.push_back(978719300);
    b.push_back(755938219);
    b.push_back(395062020);
    b.push_back(546807743);
    b.push_back(973051508);
    b.push_back(987260727);
    b.push_back(68345706);
    b.push_back(638336403);
    b.push_back(44172153);
    b.push_back(898391138);
    b.push_back(765747960);
    b.push_back(86801744);
    b.push_back(697635308);
    b.push_back(529362631);
    b.push_back(364190245);
    b.push_back(498610185);
    b.push_back(53739415);
    b.push_back(24329888);
    b.push_back(808314528);
    b.push_back(31698938);
    b.push_back(721003974);
    b.push_back(763231922);
    b.push_back(695345369);
    b.push_back(570484145);
    b.push_back(438384234);
    b.push_back(19487514);
    b.push_back(455265721);
    b.push_back(2159987);
    b.push_back(982080376);
    b.push_back(477830091);
    b.push_back(753321035);
    b.push_back(400894789);
    b.push_back(981350184);
    b.push_back(896337930);
    b.push_back(865361060);
    b.push_back(913320830);
    b.push_back(859400291);
    b.push_back(656451533);
    b.push_back(349413523);
    b.push_back(558968887);
    b.push_back(43324444);
    b.push_back(685344751);
    b.push_back(779430615);
    b.push_back(45957299);
    b.push_back(13466182);
    b.push_back(588292475);
    b.push_back(24905675);
    b.push_back(485502094);
    b.push_back(43753504);
    b.push_back(60484252);
    b.push_back(372768014);
    b.push_back(682131142);
    b.push_back(803149106);
    b.push_back(905609635);
    b.push_back(964756750);
    b.push_back(742679379);
    b.push_back(6233256);
    b.push_back(517704969);
    b.push_back(806194488);
    b.push_back(14198623);
    b.push_back(445423076);
    b.push_back(771215068);
    b.push_back(865361060);
    b.push_back(372368828);
    b.push_back(498234351);
    b.push_back(613077155);
    b.push_back(685165094);
    b.push_back(861301504);
    b.push_back(671861183);
    b.push_back(394373068);
    b.push_back(779430615);
    b.push_back(796777415);
    b.push_back(808314528);
    b.push_back(860749084);
    b.push_back(632357111);
    b.push_back(498234351);
    b.push_back(26921041);
    b.push_back(438384234);
    b.push_back(799623900);
    b.push_back(981350184);
    b.push_back(873735323);
    b.push_back(59945035);
    b.push_back(37154512);
    b.push_back(727093074);
    b.push_back(753321035);
    b.push_back(30483294);
    b.push_back(577200303);
    b.push_back(577200303);
    b.push_back(400642807);
    b.push_back(988074723);
    b.push_back(60183951);
    b.push_back(805674678);
    b.push_back(883761176);
    b.push_back(469715831);
    b.push_back(957439114);
    b.push_back(957439114);
    b.push_back(31744844);
    b.push_back(973401019);
    b.push_back(399274449);
    b.push_back(741726881);
    b.push_back(516449376);
    b.push_back(21527604);
    b.push_back(838588160);
    b.push_back(67069010);
    b.push_back(8313307);
    b.push_back(868062849);
    b.push_back(498610185);
    b.push_back(350842791);
    b.push_back(395109129);
    b.push_back(797148018);
    b.push_back(72412322);
    b.push_back(991050377);
    b.push_back(799623900);
    b.push_back(849747076);
    b.push_back(33806922);
    b.push_back(78520353);
    b.push_back(973051508);
    b.push_back(721433898);
    b.push_back(364190245);
    b.push_back(395062020);
    b.push_back(44789055);
    b.push_back(680612445);
    b.push_back(765747960);
    b.push_back(973051508);
    b.push_back(74990357);
    b.push_back(886471889);
    b.push_back(10968875);
    b.push_back(479056226);
    b.push_back(47651489);
    b.push_back(794965620);
    b.push_back(903865336);
    b.push_back(621499934);
    b.push_back(789082413);
    b.push_back(537374147);
    b.push_back(742570048);
    b.push_back(36760877);
    b.push_back(68537729);
    b.push_back(819271825);
    b.push_back(738750783);
    b.push_back(880049703);
    b.push_back(55306963);
    b.push_back(27410578);
    b.push_back(893556569);
    b.push_back(589145889);
    b.push_back(622740886);
    b.push_back(445294577);
    b.push_back(455265721);
    b.push_back(460306689);
    b.push_back(83353244);
    b.push_back(10657798);
    b.push_back(400894789);
    b.push_back(628333797);
    b.push_back(12224953);
    b.push_back(618729668);
    b.push_back(397564340);
    b.push_back(803149106);
    b.push_back(45546454);
    b.push_back(913320830);
    b.push_back(919910724);
    b.push_back(20468908);
    b.push_back(71178789);
    b.push_back(803149106);
    b.push_back(67835523);
    b.push_back(350842791);
    b.push_back(936887987);
    b.push_back(70645897);
    b.push_back(973401019);
    b.push_back(64245082);
    b.push_back(817179298);
    b.push_back(861495164);
    b.push_back(509241708);
    b.push_back(579147196);
    b.push_back(349413523);
    b.push_back(69833649);
    b.push_back(819271825);
    b.push_back(685165094);
    b.push_back(845580656);
    b.push_back(577200303);
    b.push_back(449379757);
    b.push_back(485502094);
    b.push_back(469715831);
    b.push_back(865361060);
    b.push_back(615367605);
    b.push_back(518854867);
    b.push_back(51314291);
    b.push_back(498234351);
    b.push_back(8547639);
    b.push_back(805674678);
    b.push_back(19898423);
    b.push_back(35162777);
    b.push_back(885580797);
    b.push_back(410794772);
    b.push_back(51704825);
    b.push_back(563223129);
    b.push_back(43286315);
    b.push_back(893556569);
    b.push_back(1953972);
    b.push_back(797148018);
    b.push_back(625669688);
    b.push_back(45595687);
    b.push_back(727304850);
    b.push_back(372768014);
    b.push_back(518854867);
    b.push_back(43956483);
    b.push_back(981039082);
    b.push_back(35446780);
    b.push_back(16507250);
    b.push_back(799468873);
    b.push_back(396746401);
    b.push_back(856447201);
    b.push_back(927603231);
    b.push_back(698321178);
    b.push_back(68293152);
    b.push_back(44285055);
    b.push_back(873735323);
    b.push_back(577200303);
    b.push_back(397564340);
    b.push_back(399274449);
    b.push_back(498234351);
    b.push_back(961798376);
    b.push_back(838588160);
    b.push_back(995130584);
    b.push_back(489176751);
    b.push_back(85034987);
    b.push_back(466295582);
    b.push_back(725860391);
    b.push_back(3119457);
    b.push_back(621499934);
    b.push_back(26288451);
    b.push_back(981350184);
    b.push_back(477830091);
    b.push_back(780305962);
    b.push_back(70256869);
    b.push_back(32134125);
    b.push_back(449379757);
    b.push_back(30628279);
    b.push_back(881387687);
    b.push_back(567709375);
    b.push_back(622576062);
    b.push_back(784508451);
    b.push_back(364190245);
    b.push_back(680612445);
    b.push_back(3802522);
    b.push_back(755622762);
    b.push_back(659941706);
    b.push_back(50886890);
    b.push_back(400642807);
 }

  retval = TheClass.shortest(N, S, T, a, b);
  cout << retval << endl;

  exit(0);
}