A = [
1061840 1092985 24001902 702857 501203 500018 492655 327018 325051 310792 314781 303329 313712 297130 298919 288281 279869 274980 278934 267622 265277 286730 290873 289917 282075 275007 281922 274934 355036 286500 292553 294521 292707 286977 278790 294890 282439 281510 284937 286251 287849 282455 289288 276519 296273 310334 262030 260776 262500 278423 281584 266704 267984 258051 249443 244288 258951 273412 282062 266216 262733 262587 245238 247623 254245 237722 231870 229904 228923 220291 230097 227036 234158 239293 229830 230081 234853 236666 233695 223018 216007 224615 226492 226714 220325 227130 216262 221395 217830 215900 208418 208109 205035 205645 216226 205598 192703 204205 200274 190119 199464 195410 196531 205623 198622 194645 203729 204251 195247 208044 197607 207036 196029 196164 239522 198407 186099 228573 196910 192748 172386 175769 181163 178290 178113 180257 178407 182853 181303 188354 182490 173149 180000 175848 179687 169420 174734 182528 177518 174799 183106 175097 166833 166438 177196 164271 163570 168455 164065 177579 157807 154602 157939 156490 157931 153156 154999 150620 148186 144141 144717 142639 139251 137886 140493 140907 144297 144249 145442 139341 140158 140716 136710 135131 136786 133791 133651 132745 131528 137766 130461 126701 131034 131768 136434 123387 122116 122971 115521 124791 114901 115649 111112 112430 114577 115665 111637 108670 111706 109487 106051 104903 106078 104110 102706 106242 104381 103392 104210 99247 92881 95126 92949 93972 91846 90368 87983 87615 88207 88307 86316 84509 84696 81333 79728 76936 76194 74505 74356 72765 72482 70608 73023 69130 69356 68093 68556 66361 64438 68914 65922 64053 62796 63169 61450 60591 58919 60073 59670 59024 56568 56047 56494 56192 53406 53878 51374 51713 51709 50723 50186 48061 47015 47183 46107 47820 44439 44446 44192 42909 42497 41335 42345 39995 39813 39697 38942 38750 37918 36625 35438 35457 37972 34018 32462 32382 32380 30893 30382 31348 30995 30565 31437 30477 30885 30760 28325 27054 27250 26765 26991 26789 25894 25927 24257 23458 22494 22983 22737 23121 22714 22968 22682 21848 20814 20944 23573 21001 19891 19741 19897 18566 17867 18925 17999 18138 18183 17840 16968 17177 15864 16266 16075 15812 15094 15369 17528 14309 14083 14267 13121 13352 12508 12509 12116 11823 11632 11824 11395 11050 11361 12934 10710 10816 11256 11186 10164 10698 10110 9897 10417 9579 9321 9521 10594 8793 8706 9185 8958 8751 8011 8384 7924 8220 7802 7781 7065 7350 7584 7475 7256 7116 6757 6819 7084 6832 6507 6332 6627 6740 6228 6135 6351 5099 6019 5519 5359 5994 4536 5642 6594 6034 5661 5878 5710 5559 5637 4941 4705 4523 4201 4361 4114 4141 3706 3701 3861 3449 3545 3583 3391 3241 3318 3419 3486 3321 3451 3297 3344 3441 3393 3367 3400 3248 3144 3287 2919 2983 2998 2971 2737 2818 3182 3221 3522 3080 3140 5292 3225 3347 3349 3477 3287 3295 3420 3308 3108 3519 3427 3234 2942 3078 3082 3080 2941 2879 3520 3193 3593 3543 3400 3707 4395 4038 4386 3677 3326 3582 3109 3049 3097 2510 2433 2387 2731 2284 2198 1995 2249 2165 2122 2271 2587 2765 2417 2947 2737 2026 2554 2645 2904 2596 2179 2457 1969 1863 1877 1855 1760 1329 1327 1405 2125 1574 1258 1303 1253 1591 1828 1553 1640 1507 1500 1707 1677 1598 1502 1658 1493 2659 1448 1198 1361 1277 1251 1168 1297 1058 1189 905 863 897 1170 1138 1254 1178 1296 1149 1256 1143 1233 1167 1103 875 899 912 879 873 1015 992 912 792 878 703 806 695 747 1127 777 864 845 821 918 780 812 751 779 904 797 663 731 626 680 677 569 650 611 686 742 750 859 888 1963 859 708 1341 847 798 816 785 743 903 768 788 789 703 590 622 638 627 761 729 776 782 602 538 506 561 562 612 541 536 604 614 512 447 473 407 476 408 511 442 451 499 546 620 451 492 468 469 426 424 398 478 534 595 590 640 674 580 611 540 592 605 660 686 605 607 554 553 738 768 839 1453 893 1085 943 1063 1126 2285 26166 734 553 553 530 537 483 458 546 560 530 573 420 394 472 529 576 581 516 449 487 429 504 485 436 333 327 287 382 286 303 393 394 366 391 299 347 363 404 349 375 408 470 493 405 464 322 484 427 430 461 610 557 754 627 570 597 516 562 473 534 503 509 599 633 597 676 710 628 671 676 825 775 632 617 582 582 381 394 525 379 324 340 350 326 339 339 340 374 324 298 233 119 107 157 141 137 124 152 149 225 297 243 354 242 238 213 223 270 293 321 312 315 525 519 563 493 572 598 549 453 518 584 526 336 335 359 321 352 309 226 229 270 262 336 456 459 446 492 746 670 654 736 698 626 697 705 625 811 668 655 569 535 465 486 689 429 466 475 454 487 432 606 424 421 356 509 396 391 931 263 328 345 371 344 345 335 367 367 227 198 266 194 177 371 443 423 472 567 603 361 345 471 341 352 349 437 492 505 449 407 355 327 319 254 247 322 363 341 417 394 433 517 570 507 566 532 574 665 513 612 732 699 659 644 619 643 654 667 634 708 824 683 580 561 560 594 529 383 442 465 648 576 439 398 317 297 291 211 216 231 225 239 314 278 274 301 369 305 508 470 462 390 452 450 272 250 294 275 248 262 229 274 253 274 249 242 263 270 318 268 273 247 240 218 266 233 252 246 263 231 221 345 271 265 237 257 223 288 277 312 345 382 488 584 651 613 583 590 587 511 450 473 445 490 518 551 525 494 492 461 475 573 436 439 456 454 460 447 450 355 337 347 264 319 310 295 296 297 278 318 326 274 299 239 365 279 302 217 160 171 168 193 188 294 308 254 256 313 341 401 372 411 395 417 331 393 347 493 467 590 349 311 337 248 296 451 330 1560 345 324 407 441 359 408 521 544 503 619 559 390 582 469 546 515 398 286 250 262 274 234 304 262 292 295 342 294 325 444 337 378 419 349 248 216 194 203 199 258 197 171 178 169 202 227 191 380 184 217 177 205 197 240 223 244 251 276 263 303 306 294 294 297 269 270 258 278 309 225 268 210 322 340 337 236 321 307 371 424 443 475 566 493 491 471 422 539 506 495 433 405 357 356 380 299 367 388 440 364 340 390 369 414 415 436 443 474 741 358 352 383 394 353 393 372 372 408 399 394 321 364 362 336 275 285 401 286 242 276 315 349 364 244 302 300 275 302 282 269 241 297 271 245 263 305 325 359 333 336 379 502 331 368 358 356 363 351 326 308 323 328 357 323 301 287 227 277 270 291 256 253 275 248 181 164 198 271 253 257 216 216 203 251 354 290 377 488 491 522 479 600 880 476 404 399 409 480 499 483 462 397 352 302 287 245 183 161 151 134 136 140 145 124 128 144 86 134 140 299 286 240 320 352 257 275 278 214 229 440 268 267 320 306 300 264 263 319 270 285 259 269 229 262 282 289 248 142 140 110 164 191 226 129 149 184 105 127 155 234 119 167 141 155 224 219 245 249 221 220 177 177 121 162 94 110 165 196 156 222 165 135 156 125 140 131 208 220 232 236 226 257 295 238 209 206 245 204 218 157 147 134 113 109 114 173 188 151 126 124 164 129 194 148 138 140 149 121 101 144 126 127 124 129 156 144 101 141 2415 142 79 90 74 61 71 63 77 57 61 77 124 77 77 72 77 177 186 113 122 89 97 107 117 249 219 203 213 188 218 207 197 222 205 201 187 217 186 152 138 161 169 150 122 106 128 146 146 145 126 146 123 135 135 119 102 149 165 160 132 196 91 96 71 138 126 83 75 102 109 84 88 74 83 156 168 144 132 147 129 117 102 105 89 102 105 118 122 133 84 96 158 151 139 145 137 106 98 95 129 108 132 91 107 111 152 173 161 162 134 125 139 190 144 197 118 143 134 136 134 127 132 128 159 173 227 248 249 293 283 264 310 320 307 218 318 187 148 156 182 191 178 157 151 129 122 172 144 117 123 111 79 76 143 118 84 76 137 99 124 85 92 42 46 39 31 33 29 31 27 28 30 26 24 23 19 20 21 18 22 48 37 39 43 47 50 97 82 82 106 61 78 90 106 78 93 94 110 95 104 140 117 111 149 137 105 114 144 133 120 137 149 143 140 117 126 110 97 99 118 121 131 99 98 103 58 50 90 123 164 177 162 131 185 226 127 139 165 125 141 135 121 124 126 111 113 86 90 126 90 71 33 65 26 15 29 32 36 30 26 25 25 33 35 37 30 38 50 65 39 33 43 83 99 72 72 73 53 60 53 69 47 81 93 87 118 183 153 176 141 210 215 201 214 231 191 227 136 171 142 144 156 258 229 287 302 284 273 254 265 304 273 225 290 249 229 208 131 179 151 151 143 116 89 131 123 118 147 133 125 100 75 103 169 155 120 106 141 137 211 167 93 105 50 64 67 81 97 98 117 69 83 81 98 86 102 67 45 59 60 95 137 142 186 145 145 158 127 97 113 112 168 141 130 107 80 100 81 93 94 61 115 120 123 126 150 141 135 109 118 116 122 138 97 106 77 121 94 57 65 76 89 119 119 69 91 61 74 127 109 82 76 60 68 65 143 81 90 105 89 151 152 130 114 91 108 112 104 129 102 142 126 153 116 131 159 203 216 179 208 166 243 147 136 126 128 163 186 201 227 186 150 227 253 180 174 177 139 134 107 116 107 111 110 124 137 111 95 164 226 238 233 279 207 192 162 170 188 181 191 151 136 170 183 192 158 147 111 62 85 102 80 109 55 14 12 17 34 51 82 107 115 96 90 123 104 85 101 127 158 179 131 155 155 123 100 94 95 88 137 28 32 26 22 42 38 20 17 21 21 13 19 12 16 12 10 12 6 11 9 14 17 15 34 41 53 58 39 43 11 13 15 14 41 41 35 34 81 58 81 94 81 68 33 34 42 31 73 76 93 90 94 114 117 107 137 121 183 188 112 153 146 159 124 48 61 43 59 40 55 44 49 43 41 38 27 22 20 16 10 8 13 11 12 6 10 12 4 12 2 9 7 6 7 13 23 14 14 12 24 15 17 
];
B = [
0 0 0
 535659 264542 271117
 578260 371938 206322
 515415 303123 212292
 678109 480955 197154
 436611 223940 212671
 1176306 911228 265078
 608982 398063 210919
 223104 141640 81464
 429077 295705 133372
 120737 66906 53831
 138713 71729 66984
 48887 24961 23926
 91084 36037 55047
 295204 250257 44947
 367549 240364 127185
 218147 149098 69049
 884797 791192 93605
 280961 223741 57220
 402483 337672 64811
 167301 135170 32131
 477339 366591 110748
 393405 344611 48794
 239971 143403 96568
 435121 386465 48656
 171360 119320 52040
 642672 622069 20603
 388012 348904 39108
 230892 171468 59424
 462116 401108 61008
 137738 119624 18114
 415548 400673 14875
 422058 404321 17737
 147608 129923 17685
 507146 487567 19579
 145150 132320 12830
 392547 371704 20843
 139596 127154 12442
 398743 387641 11102
 363567 353909 9658
 175081 165689 9392
 396677 388074 8603
 188650 181568 7082
 353810 346415 7395
 433694 427955 5739
 156414 149669 6745
 442810 436145 6665
 174054 169557 4497
 364691 357276 7415
 154017 149962 4055
 302381 298510 3871
 358358 354464 3894
 107002 104820 2182
 323962 319557 4405
 129858 128006 1852
 314307 310956 3351
 273389 270608 2781
 699305 697535 1770
 302321 299494 2827
 98603 97237 1366
 24589526 24509651 79875
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
1816 2071 0 0
656 462 0 0
990 786 0 0
1821 43782 0 0
753 3627 0 0
350 3830 0 0
669 4215 4 2
2420 4704 5 7
11007 2934 65 16
52440 3329 83 23
211761 3151 122 42
694564 3390 175 70
1950369 1769 238 138
4687009 815 217 159
8185526 953 232 201
8965759 1417 257 345
7440221 884 206 398
4514873 1667 264 348
1713097 1238 351 363
356569 3307 381 432
43114 4618 429 459
4479 8120 527 524
2719 4618 671 990
19914 24060 1028 1278
11173 3157 1097 922
7398 12593 2614 1285
8563 4683 1439 2980
12678 12713 1370 2600
10435 13648 1923 1976
10550 6011 1348 2117
5450 6085 1859 1991
28802 11868 1556 1679
21972 7940 2555 2303
7722 10307 1303 1385
15497 25233 1253 1246
6208 10613 1712 1370
7242 1990265 1905 2856
3191 2476 1012 1526
4457 6622 1333 1502
2828 1634 1431 2474
3029 1804 2564 2643
2892 1613 1665 1209
3262 2383 1164 1140
1194 1494 1201 1098
4754 2849 1274 1216
2251 1871 1767 1334
1748 1793 9073 7752
1386 2132 1258 1250
30143 31313 1447 1329
1250 1203 1358 1383
1126 1363 1806 3165
2352 2014 3629 1861
1106 1078 1649 1269
867 857 1830 1605
796 761 847 880
733 735 818 841
760 688 724 939
614 637 1345 2709
484 532 1382 681
1337 912 1392 1932
426 488 746 502
1303 733 820 595
1112 1424 857 1158
463 452 526 537
348 379 678 696
434 452 406 334
631 615 450 420
423 415 536 1499
462 428 782 563
473 460 547 539
1182 855 933 1958
593 628 1108 1130
751 622 714 703
2871 750 623 613
614 684 8756 8975
812 775 598 571
537 483 446 525
3381 80746 424 474
349 474 335 1983
398 332 266 358
170 161 153 152
114 250 296 257
4 5 5 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

];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 
];
