A = [
4911260 4999777 110148830 3964961 2983119 2842714 2872673 2545809 2510244 2447461 2529312 2582084 2691641 2787305 2799994 2846654 2936453 3007132 3037604 3011461 2989327 3020057 2999034 2902114 2872103 3003853 2930975 2836696 2897419 2413066 2375322 2309725 1812401 1814645 1790076 1781755 1765524 1732190 1737116 1758331 1728897 1748507 1756357 1745526 1770813 1740666 1720195 1783471 1734799 1723707 1730368 1646722 1662263 1656185 1595276 1563107 1579469 1602354 1538669 1513642 1532489 1501147 1479899 1452392 1437393 1432719 1392704 1383585 1374807 1346198 1336456 1344348 1324423 1322801 1331090 1318685 1312207 1312830 1287374 1268673 1264314 1259630 1232767 1220391 1230752 1193736 1170537 1125558 1099808 1099115 1085472 1070571 1074675 1063725 1054751 1049949 1040991 1034805 1027749 1017226 1009139 1005167 995501 992041 986733 980922 974619 964698 961499 958735 949371 948732 947737 942635 940879 935335 1027201 1029577 1030508 1120450 1144679 1145681 1144240 1150363 1151978 1145804 1139221 1129393 1114077 1107373 1096503 1089208 1080452 1071294 1059630 1052528 1039041 1031222 1020377 1010072 999774 993364 985402 974528 964415 950523 944855 935288 925891 914087 898803 889670 882056 871265 859917 850898 841517 828957 821758 812107 799331 788920 777306 770582 761184 748959 745195 730129 727159 715560 707708 698878 693454 683388 676015 666315 659754 651201 642057 633349 626631 618085 610286 600532 596849 589436 578922 574001 566045 561292 552921 544340 540220 530416 521510 517203 510797 504999 498444 490279 488999 482403 474356 468697 463194 456276 449023 442412 437364 429191 422362 418426 410359 403984 399563 392120 388216 386366 380889 375989 370021 362236 359634 352188 346338 338910 333338 326072 320021 315766 307555 303409 298502 292379 288768 282834 279660 276015 270401 265253 260733 258123 254059 249679 246273 242019 237834 235041 230968 226378 223386 221690 218292 213796 211003 206692 203490 200693 196194 193838 191272 187924 185222 183250 180178 176713 173014 171486 169653 166729 164172 162071 158704 157123 154397 151010 149288 147164 144879 143276 141307 138053 136975 133824 132090 129844 127713 126536 124358 121500 120538 118775 116542 114643 112677 111000 108897 107877 106630 103931 102773 101355 98951 97448 96309 93845 93759 91493 89936 88835 87434 86253 83855 83590 81417 80854 79174 78068 76761 75360 74606 73023 73156 70659 70439 69489 67681 66616 66269 64872 63637 62687 62425 61378 58998 58293 57784 56603 54999 55032 53708 53398 52330 51381 50717 50004 49299 48092 47431 46871 45939 45430 44591 43580 43453 42192 41841 41320 40160 40058 39348 38016 38112 37500 36385 36430 35892 34965 34209 33870 33052 32858 32277 31746 30931 30445 29851 29808 28697 28823 28140 27212 27132 27212 26109 25589 25643 25229 24601 24813 23617 23570 22887 23054 21670 21904 21312 21126 20534 21099 20542 19998 19410 19474 18933 18522 18198 17577 17482 17326 17149 16933 16338 16803 15950 15708 15447 15433 15321 15058 14519 14278 13979 13702 13455 13531 13371 13213 12802 12474 12326 12155 11735 11843 11461 11404 10952 11029 10901 10844 10289 10215 9834 9941 10143 9399 9554 9201 9127 9011 8920 8683 8658 8480 8320 8275 7904 7661 8026 7528 7371 7381 7108 6913 6896 6881 6663 6733 6578 6267 6169 6297 6250 5778 5563 5851 5680 5589 5565 5627 5296 5304 5078 5088 5222 4948 4790 4850 4506 4740 4487 4381 4349 4333 4357 4117 4088 4083 4067 3923 3713 3775 3691 3538 3595 3540 3569 3469 3353 3297 3298 3457 3275 3201 3067 3202 2970 2774 2956 2909 2747 2648 2696 2567 2635 2503 2514 2510 2494 2268 2324 2419 2232 2241 2166 2192 2161 2016 2027 2068 2035 2135 1975 1764 1901 2115 1806 1840 1858 1795 1633 1708 1658 1498 1571 1625 1591 1415 1570 1537 1509 1391 1391 1399 1355 1360 1313 1347 1419 1349 1303 1218 1309 1218 1237 1141 1167 1102 1132 1079 1102 1080 1084 1110 1053 1019 1052 989 904 917 928 908 884 928 856 810 840 894 820 772 808 770 798 759 756 736 707 806 709 737 684 683 622 704 685 751 622 652 583 635 653 633 625 641 569 542 547 599 539 522 606 599 551 549 555 575 548 548 517 494 519 488 514 495 459 436 536 446 490 481 508 463 472 521 419 394 386 479 394 406 378 421 368 419 410 361 360 386 423 401 396 337 380 325 312 359 352 341 369 351 301 343 364 276 318 309 342 330 293 326 312 316 303 272 278 304 311 298 246 272 278 263 251 281 247 253 279 271 259 261 245 254 220 204 232 234 267 279 225 275 231 228 233 212 246 252 210 219 235 241 224 236 225 186 260 221 214 218 227 202 220 186 233 193 188 205 197 197 267 181 225 192 207 198 188 187 193 189 181 159 166 157 148 173 149 195 180 211 164 174 191 155 169 176 141 154 153 156 131 120 162 149 160 171 180 147 198 158 161 152 164 154 138 146 155 123 147 136 120 157 141 186 171 167 140 154 169 166 137 149 153 109 137 129 154 168 149 131 114 119 147 129 200 130 111 113 116 116 146 149 142 141 97 119 179 137 115 129 122 120 81 129 88 125 109 119 120 122 144 116 92 123 134 103 97 110 107 88 123 123 172 110 99 108 120 80 93 96 97 99 86 88 110 109 86 75 108 87 91 93 89 122 82 69 111 63 72 89 87 85 81 95 85 67 89 122 90 71 88 89 78 66 77 90 77 89 73 90 60 87 77 87 88 70 72 78 64 66 82 82 78 92 95 67 83 91 49 90 89 102 76 92 88 95 62 66 83 93 74 74 77 86 68 73 62 64 83 119 54 92 74 80 89 67 85 83 77 86 58 77 79 76 80 69 75 71 95 82 79 83 56 84 52 82 53 58 69 73 56 67 51 81 57 54 61 74 87 54 73 62 75 71 52 67 55 57 48 64 55 42 58 66 58 59 75 44 78 48 60 66 54 63 64 44 56 46 59 73 61 60 36 69 37 39 58 51 58 60 54 73 45 43 59 53 49 40 58 53 59 56 74 42 59 58 36 59 63 41 46 43 50 54 61 81 96 82 95 110 79 112 104 114 126 145 161 112 118 131 135 135 121 121 102 94 105 93 107 119 102 81 106 109 93 114 127 109 109 118 116 148 99 114 115 105 108 109 102 120 133 108 135 150 106 163 140 262 191 173 184 193 185 210 196 191 236 1749 383 282 239 234 117 139 121 91 76 72 90 71 86 71 61 53 74 59 42 64 69 71 63 49 50 45 43 39 65 41 37 62 40 41 39 50 48 66 60 52 63 201 75 76 97 128 202 196 192 165 156 101 84 54 44 45 48 60 55 48 49 55 47 25 23 34 34 34 231 55 31 42 37 27 34 27 22 37 21 33 35 13 23 28 30 37 28 31 23 27 46 21 28 30 29 31 31 32 11 33 26 27 44 20 19 33 25 17 25 39 40 29 26 12 20 45 39 37 35 20 41 38 28 29 44 36 35 43 35 43 47 46 60 33 42 34 48 43 62 52 54 35 56 64 48 38 41 64 46 57 50 56 53 72 61 51 61 54 56 57 65 55 65 71 68 69 87 65 76 86 53 90 60 73 57 70 70 69 68 67 65 71 64 87 58 79 71 86 102 105 82 88 100 105 95 89 97 94 91 70 80 73 73 114 95 70 90 98 71 68 63 52 55 39 71 35 38 51 22 50 28 39 65 293 33 27 31 24 24 28 25 35 17 19 36 75 20 21 23 27 22 22 13 12 26 26 17 24 14 28 18 22 14 27 12 34 14 25 23 13 24 12 22 19 12 33 13 18 16 19 13 8 14 24 20 18 11 22 16 16 13 14 19 15 21 16 18 9 10 13 16 13 34 24 9 17 16 10 14 9 13 12 32 18 14 20 12 11 17 7 7 17 9 11 11 14 12 13 18 13 13 9 13 10 11 6 19 7 24 12 14 7 9 6 6 2 5 9 9 13 8 5 6 12 6 8 15 11 4 7 7 11 7 6 5 8 19 16 9 16 5 9 6 11 10 15 13 9 26 6 9 28 19 6 10 10 9 10 5 15 17 7 29 5 5 16 11 5 5 11 7 7 11 8 11 3 13 3 12 10 6 9 10 27 16 30 22 15 11 16 18 27 44 20 35 18 35 29 32 31 24 53 28 18 45 25 20 37 35 6 7 18 10 6 12 5 9 4 5 4 11 13 13 10 11 9 9 12 12 11 14 14 34 11 12 15 11 14 16 18 16 18 16 19 17 25 36 9 61 15 77 12 12 20 23 31 11 7 16 14 8 15 14 17 12 32 12 8 13 11 12 9 11 4 10 18 21 11 4 11 13 8 10 6 9 7 10 6 8 4 9 18 8 5 10 14 10 10 13 5 35 11 13 14 4 7 13 5 10 6 6 9 7 3 5 12 4 10 5 8 3 9 3 6 7 7 5 5 3 7 2 3 8 4 4 6 11 5 2 3 4 2 4 5 6 1 12 7 7 3 5 8 4 6 11 7 3 7 5 8 4 1 8 9 9 5 4 2 1 6 3 6 14 3 3 6 3 6 5 10 7 1 0 5 4 3 6 7 8 4 2 4 2 10 8 6 1 5 2 6 5 4 3 3 19 3 4 2 6 7 6 1 5 2 4 7 2 4 4 7 5 2 8 8 0 6 4 1 4 5 2 5 7 4 9 4 1 1 5 3 3 5 7 5 7 7 8 3 8 1 7 4 5 7 0 2 3 2 3 5 3 1 1 3 4 5 1 2 7 4 6 6 5 4 5 7 5 2 1 11 3 0 4 6 1 2 9 6 6 7 5 1 1 0 0 9 1 9 2 2 2 3 4 1 2 3 2 3 3 3 5 3 0 2 22 0 2 3 1 3 5 0 7 10 6 8 4 3 6 10 4 2 12 11 4 4 11 4 6 5 6 10 9 5 5 14 20 16 9 6 6 4 11 24 7 9 9 14 15 12 9 8 20 9 12 13 10 12 10 11 14 12 13 12 16 10 18 26 10 11 15 13 11 11 24 12 17 17 12 26 10 13 26 15 27 12 13 29 12 13 9 8 20 16 9 15 17 10 12 12 10 11 16 10 13 19 4 2 2 5 2 3 0 3 2 5 2 6 2 4 9 3 2 2 2 2 3 3 1 3 2 0 5 1 1 4 3 1 1 7 3 2 2 5 2 3 1 2 2 1 7 4 5 2 
];
B = [
0 0 0
 599274 451395 147879
 1686042 1448474 237568
 809154 654902 154252
 634302 508930 125372
 490501 380741 109760
 363023 280220 82803
 328967 252031 76936
 391547 317506 74041
 446543 367106 79437
 1189276 1074446 114830
 584301 497651 86650
 528982 447565 81417
 525409 448002 77407
 518115 446608 71507
 851533 763357 88176
 591475 513480 77995
 566969 488982 77987
 515511 444669 70842
 565510 484548 80962
 798405 709214 89191
 614479 528228 86251
 635601 552925 82676
 633509 545383 88126
 585462 502687 82775
 769982 676373 93609
 770444 683652 86792
 699016 603933 95083
 625808 537760 88048
 631630 541931 89699
 730606 640233 90373
 669346 580131 89215
 656080 568149 87931
 637922 555871 82051
 718960 617512 101448
 714248 628607 85641
 683668 591818 91850
 1207035 1011336 195699
 649673 568504 81169
 735794 635623 100171
 1128240 959451 168789
 717178 623607 93571
 1032474 877100 155374
 658479 579686 78793
 712519 619833 92686
 1076236 920731 155505
 729846 636366 93480
 1030149 881297 148852
 724250 635719 88531
 999193 853410 145783
 748092 659752 88340
 999350 856389 142961
 762664 670455 92209
 986467 845623 140844
 725233 639771 85462
 1043649 894466 149183
 943247 811966 131281
 701495 622892 78603
 958239 826256 131983
 615666 555207 60459
 196087421 188495833 7591588
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 
];
D = [
135 245 2 2
33 27 0 1
52 141 0 0
82 117 1 0
112 89 1 1
122 141 3 2
244 238 4 3
395 209 5 1
148058 341 14 7
1445394 441 18 10
3248557 386 51 18
7102712 771 103 62
14324304 690 1362 460
25846528 1289 6016 2222
36643316 1553 6070 3327
36141789 3229 7201 5160
27339640 4931 11437 10167
18312219 8550 17767 17314
10193823 12643 26640 26025
4317092 19351 36130 35841
1226462 24761 45273 45519
239988 34069 54670 54187
79920 46130 64694 64784
79846 60990 76398 76362
91230 78536 88866 89792
104626 95903 103224 103736
119391 114140 119062 118271
135307 132795 134773 135555
152379 151555 152091 151490
165883 168886 166742 168084
180087 182756 182222 181801
192657 197732 192527 194862
203836 208054 202777 205411
210277 213649 209082 212417
229501 220902 213893 215613
220207 218077 216282 218009
215261 221178 215955 218635
214436 217518 214622 216758
214771 217107 215241 216404
215310 216320 214489 216896
218142 219469 219024 217794
221037 223165 221635 221998
228747 231046 227297 227884
237678 236910 236689 239412
248794 249009 246534 249964
261295 260797 256889 261273
272627 271882 270305 272831
282476 282637 282065 283906
291311 292504 292186 292376
297330 297789 298185 297575
299085 299578 298554 300863
293929 295294 294936 296335
286015 286681 283716 285448
271149 274197 271734 273806
255752 256333 255941 256165
235072 237637 234281 235796
212904 214351 214127 213960
191783 192093 191079 191459
170456 170325 170183 170990
152426 151787 152315 153662
136900 137577 136886 138105
122932 123779 122368 123582
113699 113317 114888 114861
108020 107777 107474 107504
102979 103234 102714 103749
101676 102141 101488 102609
106237 104938 106098 106322
128948 136985 124997 125364
112827 112481 112438 112989
116481 116643 116483 118035
110846 110216 110264 110966
100173 101488 101627 102685
105548 105006 106467 106353
73327 73698 73518 74058
62539 61658 62052 62407
51045 50745 50640 50269
40940 41158 41361 41488
35610 35062 35289 35568
30010 30042 29998 29856
24452 24267 24307 24619
15655 15816 15747 15668
8997 8781 8794 8802
449 519 464 451
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

];x = [
10 12 15 19 23 28 35 43 53 66 81 100 123 152 187 231 285 351 433 534 658 811 1000 1233 1520 1874 2310 2848 3511 4329 5337 6579 8111 10000 12328 15199 18738 23101 28480 35112 43288 53367 65793 81113 100000 123285 151991 187382 231013 284804 351119 432876 533670 657933 811131 1000000 1232847 1519911 1873817 2310130 2848036 3511192 4328761 5336699 6579332 8111308 10000000 12328467 15199111 18738174 23101297 28480359 35111917 43287613 53366992 65793322 81113083 100000000 123284674 151991108 187381742 231012970 284803587 351119173 432876128 533669923 657933225 811130831 1000000000 1232846739 1519911083 1873817423 2310129700 2848035868 3511191734 4328761281 5336699231 6579332247 8111308308 10000000000 
];
