A = [
2122549 2649238 22067610 6021972 3456262 4807919 6857209 3764960 3850049 3648379 3559121 3492853 3326609 3194599 3125196 3034500 2885541 2799139 2742916 2639079 2525841 2447560 2361851 2330085 2336659 2286404 2169412 2004665 1818810 1431934 1352093 1201034 744717 716988 681406 663163 657559 624523 621666 608839 600065 592009 571063 561340 557337 552050 545422 541726 537146 530779 528442 523877 520954 519311 514741 510671 506673 504515 501839 498883 493309 490566 490559 486122 485857 481697 479392 477899 475483 472202 470414 467992 466255 465142 463026 460726 458028 456446 455357 450912 450577 449742 447768 445979 443525 440754 440647 439149 437071 437230 432969 432090 432221 429150 427428 426590 425090 423174 423161 420568 420148 419582 416414 415778 415847 414304 412982 413640 410754 410548 411874 407317 406648 404762 404246 405902 405656 410006 409401 411628 416225 414201 413781 410531 410318 407774 406935 405749 405811 404044 403325 403143 399435 400355 399305 397975 396503 397689 393613 394201 392369 392888 389150 388337 389825 388034 386045 386362 382687 381999 383955 380290 379448 377391 377705 377148 375147 375522 374523 373482 373081 372694 372574 370516 368350 369637 367379 368437 365447 365922 366135 365255 362481 364087 361633 360065 361463 359724 362894 359960 360198 361511 359938 364562 378155 375701 376009 377106 376080 369579 366780 365103 353882 352431 353906 352576 350494 353599 352256 351413 350431 349953 350831 349578 348712 347009 347664 347013 346136 347974 347901 346451 346255 346239 345729 346260 345607 346086 346425 346055 345524 346289 345646 346578 346587 345009 345126 346182 344948 346124 344856 345655 345369 344386 346089 343546 345144 346365 345154 346909 345436 346882 347235 346119 345420 345909 345934 344608 345343 345764 343588 344675 345064 344816 344418 344154 343982 344927 345887 346192 344038 346329 344833 343975 342771 343193 342096 343506 342902 342558 341511 341667 341063 343019 342458 340822 340080 340943 341336 339015 338532 339272 337375 335919 336890 335150 335276 335653 334454 333113 332031 330886 330446 329286 327916 328906 327762 324162 325655 323904 321694 320176 319580 317020 315266 314519 314077 313596 310281 309256 308425 306764 304367 303873 303437 301038 298097 296736 295164 293544 292169 290540 288288 286103 283726 282952 280691 278245 276213 275170 273258 271461 269003 265974 264892 264006 262409 259161 256944 256610 254024 252171 251511 247382 246406 244813 244985 242778 238418 238019 236906 233612 233752 230494 228017 226060 225652 220641 219853 217850 215539 213587 212923 210032 209719 206859 206169 202367 201977 200509 198668 196796 195374 194484 192762 190907 189933 187383 185678 184301 183260 180762 181163 179479 176412 175797 174862 172078 170522 170359 167775 166730 165429 163922 163105 162173 160731 158740 156851 156460 155497 154653 153624 152441 150353 149590 148457 146201 145697 145203 143618 142306 140851 140063 140338 138872 137457 136050 134298 132553 130428 129233 127579 126693 126551 124140 122786 122252 121207 119418 118474 117825 116965 116068 113917 113838 112327 110723 109715 109194 107561 106543 106426 104370 104292 102695 101011 100840 99538 98509 97863 96234 96152 95501 94822 92872 91255 90095 89944 89380 88886 87131 86948 84855 83752 82883 81372 81540 80069 79212 78476 77804 76262 75098 74079 72779 72577 71126 70759 70374 69578 68377 67399 67138 65152 64423 63689 62711 61640 60675 60045 59075 58632 57048 56871 55377 54643 53994 53698 52885 52007 50898 51225 49574 49199 48405 47723 46724 45622 44914 44313 44052 43021 42178 41866 40532 40178 39548 38484 38415 37495 36378 36373 35610 35099 34266 33705 33324 32612 32477 31021 30918 30121 29363 28958 28260 27662 26918 26233 25736 25557 24842 24491 23882 23437 23197 22384 22145 21578 21164 20819 20121 19712 19728 18876 18800 18327 17993 17887 17070 16941 16436 15923 15903 15630 15519 14838 14138 14302 13644 13593 13335 13174 12608 12423 12443 11862 11925 11440 11323 11034 10935 10710 10547 10403 10116 10101 10150 9755 9342 9386 9201 8909 8573 8653 8410 8275 8214 7877 7762 7603 7472 7297 7050 7088 7234 6994 6903 6579 6436 6518 6276 6167 5993 5696 5846 5757 5562 5167 5113 5363 4984 4965 4890 4780 5000 4857 4877 4834 4705 5001 4902 4783 4111 3961 4056 3909 3726 3502 3328 3403 3266 3217 3072 3048 3162 3083 3035 2940 2774 2662 2646 2585 2504 2534 2479 2407 2348 2261 2185 2167 2134 1965 2043 1957 1961 1864 1860 1869 1775 1809 1755 1699 1728 1649 1650 1666 1639 1571 1583 1590 1524 1538 1456 1554 1463 1470 1397 1434 1402 1397 1331 1370 1393 1354 1288 1321 1301 1332 1325 1327 1283 1319 1250 1359 1277 1249 1217 1209 1170 1171 1174 1150 1066 1156 1068 1087 993 1059 1063 1052 967 1039 1007 1045 1041 1002 1078 1048 957 987 964 906 955 969 954 934 1010 858 908 883 931 834 888 847 907 854 851 839 900 851 824 861 790 887 874 822 771 831 867 816 804 777 799 782 766 773 780 758 753 733 821 689 712 738 706 705 715 769 773 710 775 730 841 706 698 690 742 644 637 624 679 638 651 641 651 647 589 638 594 563 695 652 667 617 621 618 598 638 590 650 645 628 590 653 574 657 584 635 561 575 624 616 623 576 569 625 613 589 534 645 600 579 606 595 616 564 599 612 606 582 601 503 540 510 579 614 537 599 491 505 482 531 508 539 577 512 553 537 555 537 519 519 536 565 474 517 536 498 435 536 498 504 440 489 477 426 510 539 456 468 457 502 468 433 471 483 470 458 539 446 438 488 446 497 448 447 463 529 450 496 447 530 448 541 485 489 468 474 447 503 434 473 471 438 424 425 407 448 409 432 436 420 433 417 405 435 441 431 427 412 424 383 382 420 413 379 395 386 396 358 385 346 384 409 373 371 344 410 342 344 343 363 326 353 314 367 340 371 321 359 347 300 343 347 342 321 374 352 325 351 340 328 293 260 356 315 317 319 301 363 325 295 333 333 338 326 334 321 301 319 320 333 301 335 342 319 325 348 312 320 332 336 303 358 365 349 286 319 338 292 352 295 293 302 330 355 323 317 315 317 321 299 282 316 288 254 273 313 276 304 277 252 296 311 286 263 285 317 324 319 289 330 264 259 286 265 286 297 244 263 301 268 270 254 277 234 281 264 249 259 261 274 244 269 293 320 288 285 218 271 277 250 274 271 273 294 274 275 274 296 355 313 464 305 302 317 315 329 264 296 313 290 307 272 241 241 273 276 277 246 250 242 227 259 217 204 206 205 210 232 195 193 246 227 239 210 207 231 210 213 220 202 190 198 207 225 237 216 211 191 204 198 198 179 188 188 194 193 202 178 208 180 184 208 181 208 201 175 190 177 187 183 207 189 168 193 183 199 169 212 177 190 167 210 178 160 199 165 188 208 176 170 198 195 185 172 195 158 173 180 190 183 180 157 169 187 164 158 150 166 180 185 158 168 165 164 163 165 167 190 179 157 160 155 146 190 165 194 167 144 148 177 157 161 174 160 167 183 161 145 166 176 169 150 125 177 142 153 143 146 199 153 122 136 135 176 141 149 159 156 167 147 174 167 158 141 163 174 152 120 163 169 162 166 173 172 151 150 157 170 181 158 143 178 147 143 180 155 160 155 146 124 129 147 157 151 156 145 144 148 120 159 142 127 136 164 164 127 135 124 129 134 173 149 144 133 137 137 121 147 117 159 168 123 140 139 128 145 122 133 140 120 141 124 134 152 136 146 164 143 119 142 158 159 159 156 144 137 144 154 132 157 157 164 163 130 181 160 184 130 128 147 142 177 144 172 160 179 171 163 127 158 147 180 152 146 141 149 167 151 112 162 155 134 120 126 149 136 142 123 115 140 112 147 138 115 121 128 111 125 110 137 123 110 118 130 125 121 149 123 105 116 113 117 136 106 117 112 114 115 125 114 97 122 122 85 134 118 100 118 118 113 107 127 110 121 99 128 121 106 119 113 135 95 89 95 121 129 115 114 127 109 99 108 98 139 113 108 104 118 106 79 116 117 116 90 92 98 104 87 124 117 92 109 95 101 89 110 85 127 95 94 111 102 116 104 117 77 82 95 104 96 100 88 102 127 80 112 65 100 120 97 113 77 92 92 101 113 112 109 117 100 101 103 117 86 109 112 97 77 96 93 102 98 95 87 109 87 95 86 94 79 93 98 106 101 88 102 96 108 111 93 93 91 101 100 117 97 99 105 92 97 79 83 90 91 96 98 96 92 97 91 116 91 110 105 83 102 99 114 89 87 67 87 89 107 112 81 75 86 78 73 92 83 102 73 70 85 81 98 87 82 99 70 84 96 79 89 75 52 78 66 55 68 69 97 74 94 80 64 74 62 73 77 86 90 65 77 77 82 79 74 84 59 91 64 73 72 89 73 94 65 68 73 90 75 72 79 64 65 78 84 68 56 65 70 87 76 68 65 60 67 75 64 59 60 70 61 72 72 68 60 58 50 86 71 64 78 78 67 76 60 117 84 94 71 61 62 68 76 95 87 63 78 71 67 63 69 68 57 83 72 72 69 80 70 54 82 86 73 58 76 65 78 83 84 67 61 59 70 67 63 67 58 68 61 49 54 69 64 73 66 57 64 45 44 53 66 77 55 56 53 60 50 59 65 55 51 57 59 55 38 56 62 66 53 64 48 73 57 92 51 60 60 67 44 66 54 64 62 58 85 57 69 49 47 52 53 63 49 47 44 56 62 42 53 64 56 38 66 57 69 61 45 63 82 45 69 49 51 48 56 34 55 60 50 56 54 64 50 62 67 50 47 45 51 54 36 64 44 57 32 72 49 39 63 58 70 56 73 54 61 59 46 52 61 69 72 56 54 56 55 66 68 53 56 51 53 58 51 64 44 116 96 122 124 98 50 70 88 76 66 59 50 52 50 63 49 49 59 50 56 60 53 43 54 42 56 59 58 46 44 48 38 54 42 52 35 56 51 43 60 48 48 44 43 45 55 48 45 51 45 60 58 46 44 37 53 32 44 40 51 32 45 44 39 41 40 54 48 52 51 47 42 47 50 41 46 38 52 51 37 19 37 34 50 57 44 38 53 38 74 44 56 49 52 41 38 56 53 39 39 49 55 53 40 59 55 52 43 41 40 44 39 37 34 40 49 27 38 41 38 39 42 25 29 33 32 29 51 36 37 34 46 29 41 52 41 43 26 40 24 37 39 28 50 34 33 41 40 27 45 31 45 28 37 36 41 36 39 51 45 47 39 27 41 27 41 31 41 28 29 37 42 38 21 28 42 44 
];
B = [
0 0 0
 222906 183413 39493
 159135 126919 32216
 228026 184469 43557
 173513 136715 36798
 184246 146125 38121
 231555 185619 45936
 170501 139263 31238
 384199 308077 76122
 173260 145654 27606
 116177 99324 16853
 184409 165670 18739
 90012 77172 12840
 60647 53071 7576
 49919 43753 6166
 50006 41201 8805
 43855 38078 5777
 73790 61903 11887
 46908 40193 6715
 56517 47398 9119
 59806 51184 8622
 89139 75613 13526
 240960 201434 39526
 96484 85732 10752
 78133 67280 10853
 83269 73448 9821
 86126 75128 10998
 115787 102516 13271
 167121 151691 15430
 81568 73259 8309
 90986 81795 9191
 87692 79619 8073
 153025 134051 18974
 109898 99588 10310
 91838 84424 7414
 84418 77890 6528
 61941 57855 4086
 93770 86650 7120
 67021 62905 4116
 92039 84975 7064
 78143 73663 4480
 96801 90756 6045
 109033 103265 5768
 141793 127772 14021
 109594 101648 7946
 102398 94376 8022
 88222 82464 5758
 101875 95442 6433
 110474 104271 6203
 97506 93991 3515
 96265 91097 5168
 98834 95066 3768
 110597 105414 5183
 85723 82457 3266
 176067 164928 11139
 109852 105543 4309
 123717 118241 5476
 106551 102748 3803
 123607 118440 5167
 150137 145385 4752
 129709625 127558850 2150775
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
525 1053 21 14
144 222 2 4
180 272 4 1
233 310 7 5
191 316 10 4
214 409 3 10
667 552 10 5
1117 637 25 22
2661 782 230 84
8342 1015 575 316
20984 1180 753 490
63286 1699 1249 798
190419 2030 2662 1741
541251 2794 6950 4469
1374288 3955 9536 6837
3870244 5793 13216 10599
11407402 9174 17587 15511
23987214 15479 24713 23304
25235605 25102 35582 35632
18782523 38382 49840 50550
5009106 52119 66407 67241
398382 66139 82266 82842
136864 82852 97862 98170
130513 102063 112245 113572
143605 119617 128062 128466
160248 137407 142994 143109
173263 152588 156915 158589
187292 167968 172999 174516
201385 185115 188773 189239
214086 202234 202401 203233
242804 216580 217125 218533
261978 229612 232070 232446
286838 243117 245321 245198
283117 259870 261418 259419
275945 272339 271439 272575
287817 284504 284666 284831
297835 296670 295939 295407
307485 306379 306153 307403
316950 316999 316385 317611
324362 325433 325974 328138
334339 334453 335696 335527
341294 342554 341415 342493
344248 347538 344881 345707
346685 349180 348749 348768
346982 348136 349022 346767
345618 347385 354840 353301
341661 346384 338223 338769
326242 326120 324855 323688
308073 307209 308399 308978
288757 289544 290448 289378
264913 266823 265591 264289
242951 242342 241422 242583
218862 219655 226408 223629
198871 199591 199317 199297
185771 183924 189200 185691
169272 170248 168772 168595
158972 158428 159492 158365
153258 153104 152722 152600
158982 157813 151988 152483
149923 149238 157801 156642
156377 155906 154332 154136
156405 158586 151327 153775
152522 153148 159589 166940
149144 147068 149247 148684
137603 139358 148692 146558
123834 123556 129545 148035
103393 103805 114822 104621
71933 74389 82004 88059
61097 64637 51811 61070
48341 45418 37076 35442
39913 53687 19675 17852
9453 12073 37731 32615
2 0 1 1
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
