A = [
1387400 1361081 37905249 8573121 1121251 1580125 9691806 1369066 1286868 1313893 1489628 1318129 1391558 1419611 1525644 1572016 1539999 1525225 1481876 1333154 1191457 1114672 993167 878402 872233 854106 837027 806673 775416 665012 651976 601263 467407 456580 435660 442101 432096 411378 420123 411776 421858 400712 392304 386356 388448 385048 378658 380830 372574 370507 375497 367063 360219 370107 364891 355320 360709 354937 352432 351948 348095 345181 346661 340617 340369 341930 335212 335529 336109 331663 329310 331018 328135 329220 330175 325102 323577 324798 320708 316773 321449 317702 312542 316376 312920 311185 314207 309702 310664 311114 304095 302181 306628 302070 297960 302098 298915 296582 298731 294420 292419 293224 289031 290078 293496 290093 287502 287433 288174 282324 287241 283138 279469 282774 278598 278717 284551 280657 281525 284358 279451 282138 282078 274439 275647 277713 274038 272763 274680 269315 271894 270987 266770 266594 272663 265422 264664 268478 263739 260119 263130 259123 257111 258276 256938 257002 256432 253473 253536 255258 251305 251461 251889 247489 248075 249351 246322 249660 250559 244799 247020 243934 243011 242209 242637 241194 238732 240294 238229 237724 235783 234835 235515 235950 232895 230612 233591 230140 230171 230556 228007 228329 227253 226901 231267 241469 231231 232582 230670 230539 225011 221427 219560 219014 220701 218929 219506 218493 217447 217199 216514 214181 214733 214350 211818 210813 211451 209071 210936 210870 210296 208095 209577 206590 206964 206325 205244 204297 206279 203768 201923 203764 201166 201506 201531 198569 200626 200219 198439 197890 197396 195359 193991 197091 195163 193502 194948 193758 192196 193038 192805 192380 192570 189637 189500 191949 188037 187304 189347 187093 186129 185627 185015 185358 183120 184838 181514 181852 179870 181926 180089 179614 178782 178735 177790 177403 177596 175186 175796 175620 173782 172914 172708 173897 171756 171413 170019 170792 170592 169875 169858 169039 169306 166525 167085 166451 164448 165801 162826 162835 164246 164042 161395 161603 159394 161056 159651 159104 158351 156953 156627 156708 155317 154537 153663 153491 152090 151722 151483 151236 150783 150332 148808 147807 148788 146207 146148 146880 144014 144754 144144 142273 144826 139942 141988 140305 139829 138353 138841 137564 137139 137607 136059 135086 135078 134760 132283 131864 132909 131693 129932 129145 128559 126605 126300 126112 125652 125587 123726 124282 123081 121820 121586 120608 119747 119501 119303 118104 117300 116655 117099 116330 114703 113781 113942 113248 112240 110511 111526 110199 110032 109306 108495 108352 108019 107509 105783 104975 103786 104135 102534 102194 101531 102192 99566 98730 99234 98302 97251 97325 96554 97565 93729 94068 93986 94012 93643 91864 91107 90396 90601 88675 88882 87564 86561 86275 86415 85023 82694 84134 83122 82740 81378 80552 79372 79287 77995 76859 77131 76249 75175 75905 74603 72830 73685 72068 70960 70721 70316 69732 68777 68005 67895 67898 66197 65725 65038 64892 63283 62730 61937 61249 61393 60506 59968 59441 58795 57801 58098 57632 55832 55776 55304 55072 54178 52783 52518 52212 51925 50660 51280 50049 50127 49664 48456 48412 46812 46730 45715 44319 44144 43559 43735 42998 42272 41289 41351 41001 39980 40104 39156 39137 37855 38306 37047 36890 36315 35491 35546 34818 34389 33936 32962 32821 32188 31637 31288 31171 30451 30239 30224 29173 29208 28595 28305 28412 27045 27236 27219 26413 26296 25311 25654 25041 25281 24206 24449 23581 23713 23002 22602 22042 21633 21718 21062 20602 19676 18985 20077 19143 19099 19251 18367 18509 17880 17445 17514 17034 16953 15732 15582 15302 15031 14992 14372 14156 13935 13583 13523 13503 12890 12923 12734 12655 12641 11955 11906 11809 11309 11710 10585 11012 10808 10559 11200 10807 10731 10882 9917 10238 9824 9813 9683 9022 8394 8273 8016 9061 8318 8552 8040 8076 7904 7733 7867 7496 7394 7728 6461 6527 6311 5868 5887 6093 5885 5553 5570 5704 5385 5249 5121 5095 5138 4885 4799 4755 4707 4511 4631 4420 4427 4238 4299 4118 3992 4053 3942 3847 4028 3643 3794 3516 3469 3416 3429 3569 3465 3382 3996 3353 3428 3379 3003 3082 3019 2990 2894 2857 2858 2435 2532 2555 2476 2385 2420 2573 2423 2346 2558 2379 2357 2092 2232 2155 2259 2140 2105 1976 1970 1888 1828 1745 1678 1692 1605 1619 1575 1528 1518 1415 1467 1483 1492 1416 1451 1400 1447 1440 1382 1389 1355 1294 1293 1367 1224 1276 1258 1171 1183 1074 1168 1112 1067 1155 1136 1155 1308 1170 1242 1214 1231 1164 1108 1151 1114 905 890 978 939 934 867 860 873 862 860 810 817 858 822 809 742 751 796 739 793 728 740 733 775 735 741 717 749 738 804 687 715 771 787 736 677 663 724 682 705 714 683 682 731 680 692 694 587 647 708 612 570 644 582 618 600 544 557 556 550 520 603 506 573 499 577 504 518 511 523 497 512 511 492 578 510 516 473 538 496 508 487 508 502 483 497 416 448 477 468 407 410 497 478 440 481 480 464 446 478 431 438 393 388 411 430 423 402 448 414 472 454 446 420 425 417 448 410 411 383 376 381 380 426 411 430 365 402 385 406 432 386 416 384 398 422 359 398 354 379 366 369 380 344 387 362 405 378 455 382 361 370 376 344 340 311 337 349 321 352 363 335 368 308 358 332 297 319 341 323 361 361 323 329 338 328 338 302 313 357 319 357 312 311 335 311 376 301 347 287 288 281 346 364 302 329 323 340 295 284 330 297 360 300 297 341 324 316 280 274 314 247 281 304 359 296 312 297 263 283 290 301 240 281 233 293 248 302 303 291 260 259 289 239 242 272 256 269 276 257 256 267 273 272 253 263 265 259 274 288 237 272 229 251 216 229 222 257 267 207 252 286 250 246 230 243 242 258 243 250 230 206 206 217 238 245 237 250 245 218 256 235 214 224 246 202 219 208 233 214 207 228 215 226 206 212 190 223 216 200 245 205 208 210 185 212 212 199 203 217 211 219 245 203 219 228 229 203 221 188 217 231 185 206 197 226 230 210 197 215 191 206 237 181 194 176 202 215 179 180 188 183 186 205 198 174 198 186 162 186 157 180 201 201 175 202 213 202 180 198 184 164 204 160 170 179 174 162 169 159 195 177 207 158 169 181 178 184 222 171 173 204 181 180 164 186 173 180 158 157 185 148 195 183 158 153 164 181 157 203 211 142 155 142 174 187 156 156 142 141 145 158 133 151 127 133 139 131 152 155 147 138 166 153 140 176 172 141 130 128 134 138 143 123 126 153 128 161 132 143 143 133 142 131 128 139 146 125 131 132 139 145 130 137 124 107 128 134 137 144 101 116 147 138 126 125 135 133 109 114 147 146 113 113 122 136 112 118 135 108 124 117 147 125 132 102 126 144 104 118 132 115 112 123 123 101 104 110 105 111 103 122 108 106 110 101 123 140 88 125 113 141 125 111 112 123 135 132 98 124 97 109 124 133 103 129 117 135 130 127 112 127 114 110 131 110 136 115 111 87 109 122 79 114 120 122 104 113 111 97 121 91 94 97 88 93 89 88 102 103 112 102 92 82 101 110 92 95 107 83 87 90 100 109 82 104 96 104 80 94 71 98 101 85 84 112 90 106 72 99 95 85 99 88 82 87 102 85 100 87 85 96 106 86 84 87 110 82 91 113 118 105 100 100 119 106 99 108 114 110 93 110 106 118 111 96 98 103 104 103 100 76 87 88 91 80 79 78 77 75 79 81 64 72 75 74 83 71 86 79 80 87 60 75 88 83 76 84 80 96 75 107 62 73 99 95 78 69 133 87 65 63 70 81 78 79 85 71 87 94 81 88 75 74 89 91 97 74 86 93 77 86 87 81 84 94 92 81 87 87 74 86 76 78 89 85 88 84 64 58 74 60 47 67 62 63 56 61 77 73 50 50 56 66 70 51 53 60 60 62 41 53 43 60 53 50 44 50 48 54 40 64 51 47 41 49 47 52 42 48 43 50 62 59 48 54 49 49 70 58 51 51 49 50 41 71 50 48 46 41 45 58 42 54 65 47 51 49 35 43 52 42 42 46 39 50 51 57 55 36 41 40 44 44 38 55 47 54 45 41 44 44 43 45 40 43 31 54 40 37 32 36 44 54 48 40 43 49 43 48 44 43 37 45 38 42 54 70 42 38 35 45 52 31 42 47 42 37 41 49 38 45 40 37 38 44 41 36 43 57 48 35 39 46 49 49 39 43 42 29 41 35 27 48 47 31 50 34 36 59 41 48 53 32 35 48 42 32 39 48 29 35 40 44 34 34 38 41 35 30 24 41 27 40 53 38 36 27 24 42 32 35 31 32 23 34 38 30 34 29 38 57 34 42 27 28 30 36 23 37 37 35 55 38 28 29 24 35 32 35 33 36 40 28 28 32 20 47 29 27 34 34 30 35 31 30 26 36 32 29 28 27 23 26 42 35 38 24 31 29 27 34 18 31 31 32 22 19 45 26 20 33 29 23 25 28 27 26 27 32 33 20 25 20 31 21 37 24 27 26 25 32 27 28 22 20 26 25 22 22 16 24 28 20 28 24 19 16 29 21 21 22 27 24 22 29 27 24 26 20 31 23 26 22 30 30 23 30 24 26 25 25 31 26 28 17 26 30 28 21 21 27 20 38 28 24 30 41 18 31 25 28 26 32 23 18 24 30 23 34 35 28 25 22 35 14 25 29 21 19 27 18 27 28 19 20 24 22 25 20 24 22 22 28 14 21 28 24 19 20 25 25 28 21 27 27 18 23 22 24 29 22 20 32 18 20 28 33 16 19 22 32 43 15 19 21 82 27 59 33 26 29 28 38 30 22 23 34 19 35 13 21 17 24 25 14 25 15 16 21 23 13 15 28 17 19 21 28 20 12 23 13 19 11 16 17 23 23 12 15 24 26 13 17 28 23 23 19 25 15 21 13 22 23 19 23 26 17 17 16 24 19 17 15 5 18 19 21 19 9 12 13 16 15 15 15 13 17 21 15 21 12 17 12 18 12 13 19 14 20 12 16 12 12 16 16 13 11 19 12 13 17 15 18 17 11 10 11 12 17 10 11 9 13 15 16 16 13 13 18 16 13 17 16 16 12 15 19 9 17 15 18 12 9 15 15 12 20 24 12 16 7 12 13 15 10 13 22 11 9 14 10 18 10 10 18 12 14 15 15 10 12 18 17 12 19 13 20 14 10 13 17 11 9 15 
];
B = [
0 0 0
 160096 129698 30398
 105816 81151 24665
 168495 133285 35210
 130778 100957 29821
 137277 107368 29909
 177736 145540 32196
 117390 94351 23039
 302750 257782 44968
 85746 68953 16793
 70790 56211 14579
 66715 53494 13221
 73488 59343 14145
 82445 64570 17875
 30451 23231 7220
 145456 114823 30633
 43585 34458 9127
 65439 53125 12314
 54124 45370 8754
 57547 47509 10038
 63515 55181 8334
 88279 79004 9275
 234178 207003 27175
 62473 54843 7630
 63143 53966 9177
 78400 65791 12609
 50557 43445 7112
 128215 107001 21214
 117145 104780 12365
 36586 32430 4156
 50124 46032 4092
 56069 52067 4002
 151341 136082 15259
 88963 82560 6403
 61769 58192 3577
 161034 135732 25302
 37151 34429 2722
 77371 72192 5179
 34181 32185 1996
 100113 90015 10098
 33704 31650 2054
 71931 68304 3627
 82076 74185 7891
 83068 77598 5470
 212076 203164 8912
 55112 52196 2916
 74972 67813 7159
 47345 44948 2397
 146499 136708 9791
 58323 55371 2952
 90459 82580 7879
 102527 98010 4517
 53313 50228 3085
 120977 108963 12014
 161622 150263 11359
 104096 99705 4391
 56907 54004 2903
 84398 78059 6339
 59437 55803 3634
 181074 174890 6184
 99319013 97064302 2254711
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
1900 6798 5 19
300 1369 0 4
236 1833 4 4
287 2472 1 18
295 2165 3 13
376 2764 55 58
1828 3680 172 186
4874 4012 220 424
11636 4741 364 899
27967 6123 687 1957
48260 7003 1015 3564
93425 8874 1964 6962
178393 10454 9139 18519
382196 13293 28055 42767
852595 16994 40997 64644
2098698 21723 58678 93839
5082065 28820 78256 122890
10611392 40245 95210 135929
17364781 60789 105250 132899
16216424 89861 120504 134198
5656065 119802 148477 157751
750282 146811 176422 186632
272659 175484 207561 218542
288152 205403 238530 251511
322689 235559 267207 281070
353205 266503 296478 310906
378893 293606 324146 340667
400496 316540 343858 360993
406470 331047 356521 371915
408393 342063 362261 379817
411178 348196 365204 379000
408581 347786 363361 375171
406798 344662 354909 366280
384937 343939 351602 359817
359430 334906 342728 349441
345891 329333 334306 342062
334735 321233 324426 331190
322912 318622 316426 320180
311232 306697 307754 310182
301335 298414 299643 301628
290910 288374 288130 289621
280248 277990 277841 279760
265734 267576 264596 265763
253372 253045 252514 253385
242603 239477 240097 240245
226152 227508 229164 230283
212464 211985 208141 208119
190099 189902 191115 190138
171732 172996 172527 172938
155240 154942 156339 156683
147144 146278 145695 144195
126754 126323 126584 127439
116310 116623 120748 120229
111325 112084 112326 112513
105466 105422 106273 105720
98278 100049 98493 98802
95033 95791 95284 95610
91180 91805 91305 91551
94950 95523 93139 92663
90886 90170 93648 93533
91142 92221 90364 90836
92602 90207 90292 89952
91748 92185 97822 98170
89478 89254 88075 88517
85345 84490 86510 86165
72839 72748 75563 78988
60006 60398 65126 63605
48901 50130 53778 55994
47309 47018 41306 47535
37820 33470 34950 34977
34354 37336 16785 16507
10115 9652 13318 14266
1 2 0 2
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
