A = [
2437426 2323862 4995060 2520382 2456011 2405119 2315946 2487599 2504234 2609375 2849932 3153418 3657990 4119274 4575272 4916867 5304008 5770263 5826275 5732541 5873145 5937536 5837079 5740381 5757111 6648323 6654605 6628496 7363900 5958085 5932565 5820315 4497101 4528598 4473620 4454142 4420006 4304209 4278361 4258901 4211386 4220474 4203737 4192435 4215743 4136740 4087673 4148285 4049552 3998599 3987219 3840615 3863836 3847296 3755998 3679031 3690798 3716434 3573691 3488247 3503617 3425140 3378627 3320361 3279556 3275686 3201059 3136167 3109999 3044039 2999335 2982021 2935400 2911802 2906054 2866538 2835098 2811185 2750917 2691321 2657816 2624529 2562803 2524947 2515696 2456628 2397834 2313035 2259445 2230998 2189311 2151411 2126113 2090034 2062478 2036771 2009452 1988684 1964375 1930400 1905963 1876202 1847165 1823416 1799418 1779426 1762692 1737712 1719264 1698341 1675037 1670466 1648683 1627839 1619248 1604167 1879072 1885441 1873078 2144770 2152905 2138660 2115205 2092793 2069529 2047368 2021170 2002271 1975983 1953966 1930329 1896896 1871105 1845554 1823019 1799285 1774951 1758423 1738486 1715211 1693825 1672095 1649576 1626517 1601605 1577022 1562662 1539786 1520376 1504399 1481074 1461202 1439715 1419019 1398425 1378325 1355164 1339961 1324243 1306052 1289258 1271585 1254243 1235539 1215644 1198830 1181437 1166531 1151533 1135543 1124205 1106455 1091087 1077914 1062595 1046907 1033445 1018774 1007107 993572 980432 969162 957865 943235 932906 920826 905504 894138 881657 877847 862189 848800 839199 829763 817358 807149 793742 784338 773318 762900 753729 745498 736438 725607 715072 707030 697388 686577 676876 665113 655472 645455 637499 628777 621191 612433 604176 595754 588902 582148 573353 563272 557230 549479 540287 529740 521388 510469 500849 492346 485174 478167 468935 462040 454239 447213 440835 434977 428172 421411 414789 408603 401996 397552 390836 385295 379101 373258 367227 362742 356777 352358 346201 341027 337091 332108 325230 322096 315775 310427 307435 302521 298262 292698 288446 284964 280009 276059 271268 267462 263225 259785 256472 253032 248312 244519 241237 237267 233350 230988 227201 223115 219300 216571 213061 211338 206837 203869 201261 197117 194592 191402 188564 186628 183796 181061 177495 175435 172688 169104 167452 164796 162507 159679 157181 154693 152271 150489 147716 146255 143846 141339 139423 137335 135143 132946 130203 128610 127276 125422 122832 121335 119549 117688 115161 113864 111739 110994 109127 107442 105679 104146 102740 100786 99603 97694 96539 94472 93043 91760 91006 89318 88565 86574 85667 84288 82741 82304 79875 79437 77894 76530 75659 73670 73355 71954 71215 70025 69170 67648 66938 65817 64673 63806 62886 62185 60853 59993 59250 57866 57442 56440 55610 54586 53084 53347 52321 51012 49918 49349 49026 47870 47173 46382 46018 45393 44322 43783 43528 41904 41821 41084 40814 39691 39076 39093 37896 37640 37177 36486 35625 35332 34712 34355 33432 33504 32433 32260 31674 31243 30324 30191 29662 29190 29206 28604 28156 27686 27231 26723 26340 26018 25561 25185 24715 24525 23980 23582 23456 23012 22303 22256 21886 21725 21271 21096 20527 20207 19888 19708 19559 19245 18563 18640 18255 17628 17587 17524 16957 17126 16519 16460 16192 16090 15600 15442 15160 15020 14821 14258 14061 14207 13656 13847 13568 13386 13007 12881 12730 12496 12248 12040 12091 11904 11658 11220 11130 11116 10965 10749 10653 10506 10278 10001 9942 9886 9776 9488 9283 8997 9208 8877 8859 8985 8598 8473 8274 8210 8196 7954 7837 7861 7669 7318 7485 7268 7261 7119 7054 6863 6718 6666 6661 6405 6283 6221 6316 6065 6121 5965 5875 5721 5809 5604 5515 5368 5348 5282 5260 5202 5061 4898 4930 4818 4789 4672 4605 4661 4461 4454 4351 4322 4245 4192 4137 4032 4015 4067 3897 3948 3832 3805 3641 3531 3485 3591 3572 3432 3330 3384 3330 3245 3200 3173 3166 2982 3103 3005 2968 2960 2834 2884 2811 2813 2753 2679 2650 2725 2566 2707 2533 2545 2533 2429 2434 2319 2308 2334 2278 2275 2235 2173 2203 2216 2123 2139 2066 2051 1965 2005 1928 1948 1953 1899 1961 1846 1874 1813 1800 1710 1758 1761 1750 1722 1658 1721 1636 1587 1663 1594 1600 1495 1579 1489 1481 1473 1445 1416 1363 1316 1422 1409 1371 1319 1314 1257 1263 1247 1292 1209 1233 1258 1204 1224 1222 1211 1106 1174 1170 1095 1100 1080 1071 1088 1105 1042 1058 980 1048 1004 1043 1038 992 1032 1194 994 950 958 919 912 910 836 872 918 860 865 953 820 861 795 832 892 824 807 841 781 779 749 770 724 722 696 808 749 707 763 743 734 699 744 692 730 757 687 673 725 714 642 651 682 615 606 672 695 638 624 670 638 639 569 602 651 581 635 593 578 587 591 553 576 603 563 549 529 552 523 553 541 507 545 563 531 510 499 546 523 527 506 507 498 515 490 497 461 501 467 482 448 417 472 402 449 444 388 403 371 409 420 431 430 411 410 439 410 383 411 384 402 384 431 399 383 384 378 376 407 361 413 352 368 396 368 365 396 353 368 364 342 365 344 370 349 331 335 372 315 334 333 325 344 320 329 307 359 294 338 344 304 307 363 325 346 308 299 297 338 334 292 285 305 313 295 281 287 282 288 300 263 265 295 268 261 276 259 280 267 267 285 292 285 301 277 247 265 269 273 265 225 228 256 244 278 266 265 221 240 246 234 235 226 242 254 219 236 220 230 224 266 228 208 208 234 274 204 208 226 217 221 207 194 232 198 219 199 203 200 195 206 215 218 212 195 186 198 176 180 186 173 201 207 188 176 205 205 186 195 171 192 179 202 195 200 209 169 181 186 189 159 185 181 181 173 181 171 180 175 158 181 168 187 171 168 176 166 163 166 151 166 162 155 165 154 149 157 158 196 180 151 169 166 164 152 146 136 135 150 155 137 125 135 128 151 181 151 141 129 165 142 162 144 161 126 141 131 152 147 136 136 126 128 122 127 153 141 131 107 143 141 125 136 142 126 129 151 134 118 123 119 134 136 146 121 115 109 144 127 95 131 105 112 131 141 130 131 124 117 114 112 108 143 126 132 120 132 107 111 126 145 112 146 97 115 99 116 120 128 132 123 149 174 195 221 224 366 615 806 828 946 835 896 1148 931 1122 1107 1414 845 492 481 534 481 382 391 405 356 316 314 320 329 324 279 333 319 312 296 300 292 322 312 283 310 306 321 305 325 309 289 304 288 270 321 308 338 330 337 313 433 377 380 380 391 383 387 382 365 435 1071 534 446 377 380 271 288 331 225 226 200 232 192 203 205 198 210 234 182 170 185 164 155 166 166 153 139 149 152 145 166 184 175 143 179 175 217 229 225 287 521 647 590 1065 2230 2036 1632 1120 821 726 632 519 403 296 238 156 164 145 183 149 147 158 148 156 130 120 135 145 249 1283 95 86 93 79 79 87 101 79 88 73 66 58 68 71 63 58 78 57 78 66 81 86 71 76 88 84 99 81 84 87 273 231 191 160 143 124 146 135 121 114 128 108 96 121 125 123 117 127 138 115 138 171 137 129 165 153 148 159 162 171 164 172 251 246 213 219 281 248 245 292 166 170 198 197 202 211 193 201 204 208 194 208 222 207 210 225 227 226 214 214 217 221 223 212 242 213 251 239 280 263 276 265 284 252 286 242 281 295 262 261 305 289 253 267 305 309 293 285 304 273 294 332 298 328 321 355 338 352 299 283 326 258 252 263 297 261 264 271 272 245 196 178 152 153 131 140 111 145 169 126 232 167 234 407 154 143 111 114 96 88 75 89 85 115 123 77 87 73 76 71 79 84 77 83 96 115 67 102 100 92 68 71 105 88 110 106 110 106 133 125 116 113 112 126 119 113 138 90 87 96 81 106 94 117 96 124 112 113 127 116 135 268 190 227 202 191 251 218 291 265 264 334 397 265 166 86 84 87 69 74 72 66 66 326 98 71 74 73 59 48 50 59 65 65 53 44 59 61 55 65 65 53 51 50 41 46 47 30 38 41 50 33 43 30 41 45 43 47 47 41 50 35 37 40 37 35 32 35 48 41 39 41 47 30 37 42 36 34 51 33 32 44 31 33 27 40 32 35 27 32 41 46 27 39 46 50 43 39 36 29 35 31 36 22 37 27 27 31 37 24 18 26 35 16 26 25 29 25 30 29 34 37 26 45 43 28 43 43 37 29 37 28 42 51 41 43 34 24 46 36 39 46 39 46 47 50 43 49 30 53 57 44 48 60 34 48 48 52 54 55 47 63 39 69 54 56 56 57 54 77 63 41 60 63 64 47 69 61 50 61 55 59 59 47 54 56 68 58 61 56 59 61 48 65 67 65 57 52 58 49 56 68 62 47 48 48 47 42 49 58 46 62 60 38 47 54 45 45 57 54 65 50 62 51 38 47 43 43 46 45 36 47 34 33 41 36 37 50 42 48 57 52 64 51 60 50 41 45 34 25 23 35 28 30 25 20 28 21 23 13 17 13 20 22 14 14 20 12 10 13 14 14 16 17 17 14 15 17 17 20 14 8 15 15 18 11 8 10 10 16 14 14 8 10 7 14 15 7 11 10 15 19 10 10 7 9 18 16 17 14 17 9 13 5 12 10 18 13 6 13 14 14 13 8 11 11 17 11 9 15 10 10 8 5 10 13 13 10 9 6 11 15 4 15 11 10 9 6 9 9 7 8 4 7 8 3 7 9 7 11 5 3 10 11 8 8 7 9 9 9 6 9 6 7 4 9 7 7 10 9 2 4 5 8 8 12 16 5 3 10 8 13 10 8 7 15 6 10 7 5 2 7 8 8 10 8 9 6 7 10 8 9 5 9 8 5 6 11 7 5 9 14 9 8 5 8 12 9 7 5 10 8 7 5 6 7 5 7 12 7 8 10 9 12 1 8 10 6 11 10 8 8 8 5 3 7 8 5 15 7 10 4 8 8 12 15 8 10 8 12 11 5 10 4 6 6 10 12 6 2 10 7 6 15 18 9 13 12 9 15 13 10 9 10 7 8 6 9 5 11 11 8 8 6 5 3 8 11 6 6 6 3 13 9 5 11 10 12 8 8 12 11 9 7 3 8 7 7 8 4 9 7 8 6 5 6 7 10 7 11 9 11 7 5 4 3 7 13 4 13 8 4 7 13 9 7 6 4 4 8 9 8 8 6 5 5 3 4 10 3 14 4 6 6 4 10 8 5 2 8 7 6 3 6 5 5 2 3 7 6 8 6 1 2 5 9 7 4 5 6 5 5 3 6 5 
];
B = [
0 0 0
 901065 618642 282423
 1848074 1381336 466738
 1241746 928689 313057
 1036671 757220 279451
 908990 665132 243858
 722806 532308 190498
 664821 493798 171023
 649555 494342 155213
 680761 518729 162032
 1363800 1083231 280569
 918008 730040 187968
 851131 670161 180970
 809022 634584 174438
 778947 614450 164497
 1085810 879857 205953
 892214 714411 177803
 956280 780559 175721
 829478 670625 158853
 880585 708489 172096
 1090467 892378 198089
 970606 789008 181598
 995745 820314 175431
 977481 801691 175790
 952868 779657 173211
 1134902 936098 198804
 965672 790656 175016
 1111841 911438 200403
 980944 813366 167578
 1051648 867925 183723
 1106252 919113 187139
 1114801 924388 190413
 1083492 899397 184095
 1064057 887625 176432
 1333612 1103931 229681
 1087674 909338 178336
 1114313 923562 190751
 2819266 2311873 507393
 1063912 890792 173120
 1320897 1102921 217976
 2426428 2001096 425332
 1273374 1062603 210771
 2198575 1818044 380531
 1080751 909350 171401
 1285993 1077512 208481
 2255853 1874867 380986
 1295524 1089090 206434
 2174902 1804682 370220
 1274519 1073462 201057
 2108095 1757817 350278
 1291831 1092817 199014
 2087285 1743927 343358
 1365326 1152388 212938
 2087500 1746223 341277
 1302543 1102750 199793
 2222744 1864224 358520
 1962776 1647037 315739
 1216143 1032699 183444
 1954408 1641273 313135
 910558 783078 127480
 208020689 188949731 19070958
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
38 78 1 3
16 13 0 1
23 12 1 0
36 33 1 2
31 35 1 4
54 28 3 3
100 64 2 6
637 85 13 6
367750 112 20 8
2443396 156 28 13
4238175 184 63 21
6947986 274 108 72
10288435 390 949 349
14818478 607 3492 1800
18411020 1113 5556 4066
20922488 4751 12024 11189
19517872 8423 31714 30820
14514198 17963 58367 57508
9243902 31306 87290 87548
4688501 48807 127203 128147
1872045 69645 157288 158027
642324 98298 191658 193800
297195 140396 221598 223379
263568 189682 254529 255807
281618 251582 288385 290435
311426 316152 327188 328859
346085 387101 370386 370495
386577 450236 419077 420156
430621 510339 465868 468480
472992 564113 511043 516430
509520 608609 551132 554424
535071 636993 580878 584995
560776 666948 607157 612389
573856 673955 615497 619982
581030 675126 623020 626927
583873 668941 620632 624716
575379 649493 609916 611247
575617 635730 602747 605599
576120 627190 599433 600376
578683 619567 594166 597911
579578 611431 591379 595850
583214 610219 594852 597403
594823 614322 601768 607323
608295 623648 614939 618110
630107 643391 634103 637791
657698 668483 661726 665237
694918 702513 696156 700208
730709 737885 732678 737342
774475 781167 774030 779953
818789 824188 819416 823047
857019 864234 858455 863780
888355 892075 887468 893286
906045 908856 905647 911403
913677 919181 913523 919084
905509 910684 905626 911153
878884 883116 879204 884793
835213 840895 835804 841494
780902 783853 780400 783921
717214 718440 715930 719806
647490 650135 647387 651919
584139 585653 584198 587329
522598 524364 524114 526837
463553 465299 465008 466664
412987 413981 411874 414548
379371 380422 380754 380461
360953 361514 360552 362171
359033 358702 356484 359554
341487 342804 340152 342443
327791 328422 326786 328996
328601 328865 327607 327990
318183 318361 317349 318652
303419 303121 302858 304818
278389 277494 277578 278294
244926 245227 243075 246076
211732 210382 209743 211358
174037 174229 173419 173473
127170 126581 126785 126995
88929 89449 89321 89950
70207 70529 70239 69989
48650 48232 48340 48292
26052 26160 26027 25739
11715 11909 12063 12049
629 712 666 611
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
