A = [
207635 207617 1350291 213758 199964 193252 192544 194024 180771 174482 179691 178780 179645 176489 176855 176328 177498 177744 173897 174417 173503 171866 169704 168054 168694 168842 171282 169557 170421 167878 167948 168722 164976 164794 164294 165651 165918 163598 163943 161700 161509 159093 159906 157679 158806 157455 156029 157990 154030 154919 155676 151642 153921 151561 150936 153773 152056 150164 149049 149700 148599 145572 145861 145481 146025 143991 144435 144762 143874 142402 141524 142407 139828 139239 139183 137647 136899 136891 135660 134226 133904 131477 131617 130749 129194 128451 127759 125832 124911 124478 123428 122368 121557 119863 119845 119562 117255 117591 116502 114994 115489 113666 112837 112139 111825 110712 110277 110274 108101 107843 106057 104911 105012 104717 102773 102079 101997 100799 99989 99536 98826 97869 97248 96644 95868 94739 93809 93402 92831 91858 90646 90232 88907 88769 88676 87474 86514 85735 85474 84045 83522 83027 82160 82359 80690 80421 79441 78593 77994 77532 76721 75748 75366 74521 74119 73722 72304 71759 71638 70531 69995 69110 68122 67930 67347 66307 66105 65371 64908 64468 63402 63003 61687 61668 60739 60737 60090 59597 58705 58762 57260 56840 56743 55871 55126 54732 54241 54099 53334 52743 52355 51966 50925 50733 50340 49373 48666 48879 47735 47287 46874 46397 46091 45393 45279 44451 43737 43664 43134 42511 41805 41442 41129 40596 40317 39844 39233 38752 38342 37978 37558 37310 36571 36322 35646 35107 35013 34266 33717 34093 33642 32620 32734 31654 31415 31358 30614 30310 29932 29579 29406 28921 28672 28083 27834 27397 27212 26767 26233 26228 25756 25133 24460 24699 24456 23999 23677 23349 22935 22823 22404 22257 21601 21994 21198 21010 20203 20401 19855 19649 19585 19316 18962 18796 18222 18166 17790 17444 17445 16867 16959 16578 16493 16168 15656 15693 15430 15099 14755 14501 14531 14154 13958 13981 13655 13596 13264 13033 12799 12614 12332 12180 11867 11743 11415 11467 11235 11231 10834 10703 10577 10456 10209 10072 9721 9847 9661 9409 9409 9290 8926 8749 8737 8589 8332 8325 8255 8074 7903 7671 7642 7452 7467 7279 7187 7107 6923 6833 6511 6688 6438 6313 6228 5965 6057 5910 5900 5803 5610 5507 5614 5338 5182 5202 5199 5037 4963 4956 4825 4725 4709 4446 4511 4458 4282 4137 4188 4124 4060 3891 3883 3876 3815 3771 3530 3510 3452 3450 3370 3272 3237 3199 3083 3033 3033 2986 2883 2844 2858 2838 2658 2652 2554 2562 2610 2566 2487 2298 2406 2345 2187 2230 2208 2240 2194 2080 2092 2087 2003 1906 1967 1937 1793 1889 1821 1806 1816 1714 1780 1680 1699 1596 1630 1608 1538 1482 1511 1479 1564 1418 1384 1411 1378 1406 1369 1330 1269 1356 1252 1253 1220 1272 1195 1201 1112 1132 1151 1019 1094 1079 1143 1035 1031 1015 1028 1022 965 1011 956 928 953 906 891 863 842 880 814 840 827 900 787 808 779 765 798 752 786 745 675 770 722 709 721 636 677 670 693 666 615 672 640 600 577 595 585 586 547 572 556 582 599 581 531 524 540 532 509 537 504 499 497 497 494 521 477 518 482 514 450 483 461 461 431 468 469 454 416 479 464 415 446 383 430 427 424 379 436 377 405 402 380 417 395 373 394 404 364 383 375 391 357 376 348 346 373 370 368 361 361 360 349 294 341 351 309 327 348 325 321 314 321 369 291 341 322 339 303 298 321 309 318 335 293 285 325 302 286 272 292 280 266 271 276 305 298 264 266 266 258 246 261 237 300 309 263 297 275 269 240 330 289 262 259 275 259 274 254 229 292 245 245 215 249 223 225 250 245 297 229 223 260 231 237 240 256 216 215 209 217 218 208 228 232 237 239 222 209 228 212 206 204 203 237 199 190 184 187 185 205 215 174 188 193 219 181 217 181 168 201 210 182 189 229 171 200 206 193 174 180 191 166 179 196 169 196 186 170 159 177 160 189 177 157 171 189 187 160 186 197 189 149 185 158 184 170 168 155 172 157 167 159 151 176 159 163 177 152 151 172 170 155 146 132 168 152 140 137 150 149 134 141 114 145 141 124 129 114 122 149 133 130 158 136 150 151 173 113 137 137 157 133 139 134 143 132 138 199 154 149 163 149 126 137 156 145 147 129 165 146 158 137 113 158 130 110 145 123 134 146 144 119 126 110 98 106 124 123 111 105 90 114 125 123 88 112 106 115 87 96 125 94 84 94 93 101 115 112 98 108 101 91 98 107 81 91 90 89 100 103 74 85 90 98 87 101 97 103 89 105 99 78 83 89 84 78 90 96 88 85 75 79 94 90 81 71 71 81 65 77 82 73 80 68 85 109 82 90 76 63 72 76 80 78 90 88 96 85 78 67 86 74 92 67 78 57 77 95 60 75 57 83 77 66 73 62 76 61 69 62 75 54 69 62 68 81 59 74 62 67 69 60 62 68 64 56 66 55 65 67 69 50 61 48 57 57 59 81 63 75 59 51 61 48 60 64 50 50 59 61 62 52 61 46 56 54 54 64 49 47 59 58 49 52 57 61 75 78 65 85 99 85 103 107 99 82 100 106 69 92 99 103 103 110 88 96 128 132 101 124 102 117 137 141 84 110 99 113 115 131 131 119 120 122 122 61 81 75 86 87 68 157 86 66 85 98 64 73 66 72 43 46 53 63 50 48 45 40 41 52 57 56 57 46 46 167 60 50 44 54 52 34 36 59 53 46 49 35 48 44 46 29 42 37 33 37 47 39 49 36 47 63 34 45 38 41 38 41 29 44 43 36 48 35 48 40 36 53 95 39 46 61 82 73 55 76 70 39 66 43 53 51 71 73 46 85 53 60 43 77 53 65 62 45 61 53 47 64 66 51 129 81 76 69 65 65 75 32 84 75 59 55 52 93 123 106 39 72 72 55 35 34 36 49 39 28 57 57 42 52 49 71 76 69 131 67 91 81 127 79 85 79 90 84 82 84 52 36 84 86 55 84 55 66 108 76 105 108 77 22 18 22 19 24 27 20 41 18 28 82 34 32 21 28 34 19 30 21 27 21 20 23 29 31 11 17 25 19 21 25 15 18 19 21 23 22 33 16 14 20 24 19 17 21 17 30 25 28 26 23 12 16 17 20 25 13 25 17 21 23 23 20 13 20 16 20 18 27 21 21 12 29 18 27 23 22 26 26 11 19 34 30 26 24 23 23 19 20 23 19 23 18 28 15 26 21 31 21 28 22 31 25 21 15 33 23 16 20 15 16 11 18 15 15 5 23 40 11 24 23 23 18 22 23 24 33 23 18 31 18 24 22 19 25 22 17 6 19 14 21 9 12 9 12 9 19 13 13 31 14 15 14 8 14 16 9 9 7 17 11 8 12 11 10 12 5 5 22 11 17 13 14 11 9 7 11 14 19 13 11 10 8 14 12 15 9 10 10 6 10 9 10 12 5 7 8 10 7 9 13 11 9 14 5 10 9 14 17 7 7 17 15 10 8 7 7 12 12 16 6 4 6 11 11 14 13 11 15 9 12 11 8 9 6 11 13 6 12 5 9 9 9 8 3 12 9 7 7 12 11 4 4 13 6 8 3 4 10 6 11 9 6 9 7 7 7 9 5 10 6 9 8 3 6 9 7 5 11 5 9 7 10 3 12 5 6 4 3 7 6 8 7 8 6 5 5 9 4 4 5 8 10 9 6 10 6 4 7 7 7 8 5 8 2 9 6 4 5 10 10 4 8 3 5 9 4 7 4 5 7 6 3 6 8 7 12 5 8 6 8 10 5 11 8 5 4 6 7 9 6 3 7 7 8 5 6 8 5 3 4 7 7 4 7 4 9 4 8 6 5 6 3 8 1 7 10 6 9 8 7 5 4 8 5 6 3 6 2 5 2 5 5 2 5 5 6 5 3 5 2 3 4 8 5 5 2 1 1 6 8 4 6 7 5 1 5 4 3 4 3 3 3 4 2 9 6 4 4 7 4 5 1 4 2 3 3 6 0 3 4 3 7 3 2 6 1 9 7 5 3 1 5 4 3 7 2 3 3 7 4 4 7 5 2 1 4 2 6 4 4 4 2 5 4 3 2 2 5 3 3 8 3 2 3 2 0 3 3 1 1 3 4 2 3 3 1 1 2 3 3 5 4 0 5 3 7 3 1 3 6 1 4 3 1 0 1 3 3 7 4 2 2 2 3 1 2 3 7 4 2 2 2 3 1 1 2 2 4 4 2 2 0 3 4 0 3 2 1 2 0 1 2 4 1 4 2 5 3 2 1 2 3 5 2 3 0 1 2 2 2 5 1 4 2 3 0 0 5 0 1 3 1 2 7 0 2 1 2 2 2 2 1 1 3 3 3 3 4 1 2 3 2 1 5 0 5 2 1 0 1 2 0 3 3 0 1 1 6 1 3 2 2 1 5 4 1 4 3 0 1 0 3 3 0 3 2 0 4 4 0 4 3 1 0 0 3 2 2 1 2 2 3 3 2 1 4 2 0 4 3 2 4 3 1 2 0 2 1 1 6 3 2 2 3 2 2 1 2 2 2 1 2 1 2 2 1 0 2 1 1 2 1 2 2 1 0 3 5 1 4 1 0 1 0 0 2 1 0 2 4 3 3 2 2 2 3 2 2 1 1 3 2 1 2 2 0 2 3 0 2 1 1 1 0 1 5 2 1 3 1 1 3 1 3 4 3 7 1 3 0 1 3 0 2 2 1 0 0 1 1 2 1 1 1 0 1 0 1 2 2 0 1 1 3 2 1 1 2 1 0 1 2 1 1 0 0 0 2 1 1 0 1 2 2 1 1 0 1 0 1 1 0 1 1 1 3 1 2 1 1 0 2 1 1 0 1 0 1 4 0 0 2 1 2 0 0 2 1 0 0 0 0 1 2 0 0 2 1 1 1 1 1 1 0 2 0 2 2 1 2 1 
];
B = [
0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 32215 30059 2156
 56040 52685 3355
 13875 12647 1228
 135463 126550 8913
 13664 12796 868
 28779 26675 2104
 21094 19764 1330
 46209 43365 2844
 2551 2220 331
 164803 154779 10024
 109 88 21
 5450 5018 432
 2021 1756 265
 28296 26162 2134
 3052 2827 225
 2781 2552 229
 9484 8864 620
 6425 5742 683
 267049 251387 15662
 30201 28410 1791
 3094 2834 260
 15251 14457 794
 7375 6863 512
 7674 6983 691
 292239 275711 16528
 4404 4025 379
 66696 64433 2263
 10039 9633 406
 9530 8832 698
 11588 10295 1293
 13022556 12660539 362017
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
17 13 19 13
5 0 4 1
18 3 6 7
37 7 16 14
26 5 20 11
15 9 53 20
722 4 118 39
3109 12 132 64
9311 11 187 87
26902 17 239 106
58548 17 300 132
137830 25 342 166
294598 36 372 234
646470 63 486 273
1380203 102 568 361
2444194 133 650 512
3217800 215 672 601
3079837 256 564 603
1848101 345 603 676
520712 436 644 757
73106 538 661 815
4654 609 745 836
1088 725 786 780
906 876 823 720
792 846 798 703
822 828 649 710
866 940 647 716
810 872 663 686
853 947 675 867
672 752 587 762
693 787 601 678
690 796 580 721
643 751 536 669
701 773 616 664
1019 1083 683 1069
1521 1619 905 1265
798 3965 721 1802
352 359 352 335
340 368 379 323
358 366 365 384
424 371 374 370
373 375 376 409
455 430 385 385
389 417 374 415
455 466 433 409
449 439 432 461
450 454 441 435
445 452 435 451
409 392 440 427
414 426 410 377
394 417 418 386
361 343 340 361
359 334 328 333
310 309 280 281
247 262 283 271
216 244 249 217
220 199 249 224
191 215 223 231
203 171 202 212
180 184 203 189
192 174 197 203
191 204 218 200
195 162 191 217
205 210 215 194
232 218 226 214
248 262 266 235
250 305 244 298
323 326 321 322
375 317 322 313
322 349 397 382
406 400 438 434
438 435 484 451
427 491 513 472
529 553 516 463
537 505 520 539
520 522 535 537
493 470 518 507
464 479 469 460
472 524 525 540
459 463 427 446
303 313 340 369
190 197 191 214
15 12 11 20
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
