A = [
887538 859282 1776742 956816 922963 907571 875642 936670 947225 994253 1094657 1241094 1468249 1694161 1906243 2057004 2251617 2481687 2513684 2494956 2572898 2607546 2574017 2540771 2552290 2790448 2744027 2669845 2810516 2254305 2228712 2143074 1580793 1586443 1565972 1553412 1539685 1507839 1498703 1497485 1481357 1489246 1488921 1485189 1494303 1468154 1452951 1474533 1439824 1424113 1417277 1366746 1375698 1369494 1339803 1314108 1320683 1333228 1283197 1251732 1260966 1228525 1213485 1193346 1183209 1179045 1151914 1133826 1122401 1099702 1082164 1078187 1065822 1055379 1052293 1042505 1034068 1023048 1003430 986971 973544 962962 940065 928659 926611 904056 886073 853470 838485 825869 811679 796542 790523 777293 769563 759794 749756 743068 734256 723555 713002 701965 692930 683805 674119 668776 664898 654079 648145 640421 632057 627546 621080 613873 606467 603905 688821 691420 688274 775988 778059 774826 768358 765092 752525 744698 738397 730922 723835 716177 708676 696233 688337 683859 670474 665125 657355 648284 644840 636373 627956 621511 615095 604793 598549 590126 585842 579880 568496 575785 555827 550095 539959 534656 527581 521085 512454 508696 503208 497252 490897 481129 476164 473410 465703 460097 456593 447747 444014 436892 433788 426664 420646 416324 411037 404656 402288 395701 392453 387199 381011 377520 370022 367064 364143 359568 354575 350545 343948 364229 339195 332410 330608 326998 322037 320461 313583 309095 305565 302336 298678 296159 294108 288891 285593 281227 278953 274370 270612 264921 262865 258666 255473 251809 250887 245099 243085 240235 237396 235047 231065 226515 223765 221887 217118 214154 210531 207364 203399 200045 196556 194154 190360 187946 185448 182381 180281 179109 175398 173179 171414 168111 165611 163724 161563 158986 158198 154585 152448 150839 148617 146656 144762 142769 140183 138488 135445 136029 132490 129715 129062 127086 125788 122506 120736 119408 117328 115916 114095 112355 110764 109087 109421 107384 104482 103233 102066 100122 99026 96984 96305 95255 93622 92221 90648 90128 89011 87317 86263 83521 83935 82333 80728 79728 78952 77772 75782 74938 73868 72110 72320 70443 69755 68661 67348 66263 65430 64238 62919 62748 62232 60750 59269 59184 58318 57078 56140 55557 54620 54003 52464 51952 51338 50859 50000 48883 48745 47783 46787 47052 45653 45519 44155 44378 43168 42232 42071 41331 40539 40157 39840 38838 38291 37589 37364 37290 36384 35986 34647 35046 33848 33558 33680 32519 32090 31440 31388 30925 30535 30063 29183 28905 28316 28231 28109 27396 26798 26176 26107 25500 25420 24853 24067 24056 23641 23487 22589 22219 21685 21281 21170 20514 20379 19770 19931 19467 19025 18844 18775 18254 18325 17715 17827 17284 16862 16925 16205 16141 16160 16029 15429 15341 15021 14796 14481 14562 14188 13733 13786 13384 13263 12884 12898 12749 12524 12414 11878 11915 11702 11598 11590 11322 11185 10820 10635 10593 10325 9892 10142 10001 9662 9535 9492 9279 9231 9112 8975 8773 8524 8411 8489 8460 7785 7949 7755 7752 7525 7505 7289 7419 7217 7080 6979 7024 6623 6621 6391 6326 6348 6170 5909 6181 5890 5815 5815 5717 5443 5378 5363 5342 5060 5002 5149 5002 4819 4813 4630 4943 4688 4502 4460 4425 4407 4128 4079 4205 4080 3997 3900 3699 3771 3684 3669 3653 3449 3429 3399 3387 3385 3176 3284 3178 3082 3045 3103 3032 2914 2878 2825 2759 2824 2676 2654 2671 2570 2402 2559 2512 2541 2380 2346 2313 2414 2239 2167 2119 2157 1999 2071 1979 1998 1900 1929 1896 1902 1824 1761 1881 1743 1727 1648 1685 1725 1603 1715 1570 1583 1636 1494 1570 1452 1533 1439 1384 1376 1428 1371 1324 1283 1357 1343 1227 1197 1209 1193 1158 1152 1107 1124 1163 1055 1082 1077 1020 1035 1053 1005 976 892 1042 958 948 877 902 876 890 814 878 873 830 804 814 760 799 793 789 702 702 735 709 688 679 676 692 689 698 654 642 665 583 616 633 563 612 612 608 570 588 575 600 543 556 578 521 524 517 476 461 494 462 476 499 439 472 450 463 440 414 436 424 421 447 380 419 422 407 395 422 410 411 349 406 376 393 448 325 321 333 352 328 330 320 327 309 296 316 311 317 278 303 319 285 290 274 269 311 344 263 255 255 294 270 267 275 311 252 262 238 235 227 257 234 285 246 202 233 251 224 238 238 220 221 261 207 227 233 254 218 201 182 195 181 220 219 216 193 228 225 202 158 186 208 167 226 189 204 166 182 172 204 184 169 184 177 171 151 183 163 161 167 175 171 171 166 201 170 185 164 195 165 193 179 164 152 148 151 134 154 122 139 142 116 146 130 116 139 112 137 147 146 137 110 155 137 98 134 157 126 107 143 140 125 118 113 126 132 122 132 108 134 116 103 110 125 120 132 107 116 115 129 107 120 113 107 125 95 95 114 91 112 105 109 88 129 111 107 136 94 97 97 120 123 96 91 84 117 116 84 95 92 102 95 87 83 103 107 97 79 105 93 81 86 84 75 101 83 91 93 119 72 100 78 80 88 86 69 78 78 87 63 74 113 96 85 86 86 68 72 94 83 72 107 99 79 79 91 72 76 99 70 68 73 99 63 63 83 68 73 51 66 67 72 76 65 60 58 68 67 75 70 56 70 55 61 65 51 47 52 64 75 71 58 54 64 53 70 50 75 56 72 69 60 77 55 60 47 61 53 72 64 68 75 59 58 51 53 60 71 51 57 59 62 46 44 65 52 50 64 61 42 61 59 65 55 62 51 64 43 55 61 53 39 56 47 41 47 57 42 44 52 37 60 63 55 49 32 54 60 47 43 47 35 39 44 41 40 33 44 36 42 36 58 56 30 60 34 35 45 50 42 44 34 38 46 45 36 35 41 52 60 48 39 49 36 45 36 37 36 39 45 45 55 45 42 35 43 33 31 40 45 42 52 55 49 23 26 33 58 36 52 32 45 45 31 48 36 34 32 24 54 50 32 58 38 37 40 46 42 44 64 63 58 57 62 66 77 57 64 58 53 62 53 65 47 60 51 30 57 53 50 54 54 44 57 47 39 46 61 27 53 27 60 46 37 46 55 41 53 44 42 43 47 52 61 50 86 78 61 59 63 66 59 56 73 67 552 111 96 67 98 46 41 41 33 51 32 35 33 35 26 36 36 38 39 35 37 29 28 27 33 34 29 21 32 23 26 38 30 29 21 20 28 22 16 26 30 25 23 34 44 59 41 71 107 89 50 76 59 34 40 22 20 21 45 32 27 35 23 36 23 25 26 21 25 94 27 26 30 23 15 21 20 21 21 22 20 10 19 27 13 18 17 23 26 32 30 37 23 13 33 22 16 15 24 23 22 13 19 20 30 18 36 17 34 20 37 24 13 16 24 39 10 16 32 25 23 31 32 28 30 30 29 27 37 35 25 26 15 31 20 23 22 27 30 37 35 39 39 34 35 40 53 36 24 35 34 43 41 37 50 64 76 48 50 43 51 42 39 43 38 42 36 39 54 48 54 48 66 43 40 46 57 71 67 62 61 51 62 59 72 52 72 77 81 77 65 58 85 86 76 86 82 76 83 66 73 63 87 67 71 82 76 76 68 74 51 58 33 37 34 32 33 19 25 15 17 31 22 24 22 30 23 27 24 22 19 18 17 21 22 13 23 15 8 10 13 23 13 13 19 15 15 11 19 9 15 16 12 9 7 5 10 10 10 14 9 14 14 19 9 16 11 10 6 8 8 9 8 13 11 19 8 11 15 9 8 8 8 10 14 12 9 13 14 17 6 17 21 6 11 7 19 21 9 14 12 12 13 21 22 9 18 15 15 16 6 17 13 15 11 11 16 12 10 19 19 17 22 13 9 8 11 8 8 6 20 14 4 4 16 9 8 11 8 9 16 11 14 23 12 8 5 17 10 14 19 17 17 10 11 11 7 10 25 12 14 12 8 16 11 20 11 10 13 18 11 18 15 10 11 25 17 7 11 15 14 9 7 4 19 14 10 10 13 16 17 2 12 6 14 16 16 10 8 18 22 9 17 15 10 11 11 17 12 18 13 4 25 9 9 16 11 8 9 7 10 4 9 10 4 10 17 18 14 17 16 8 12 13 24 19 11 18 19 24 12 19 9 18 26 17 22 22 19 24 15 19 25 36 21 15 17 13 27 28 12 24 26 15 24 16 18 16 13 23 24 30 21 26 32 20 29 19 18 5 7 9 13 7 8 12 8 9 5 6 7 11 13 10 4 8 6 7 7 15 8 14 5 9 2 6 3 5 6 8 7 6 8 5 7 4 2 9 2 9 5 11 8 12 9 10 11 7 9 8 4 8 5 9 9 4 10 4 4 0 1 6 4 6 1 6 5 1 5 2 6 2 2 9 8 9 7 6 8 6 4 0 0 3 8 3 2 0 1 6 4 6 3 3 3 3 4 7 5 2 4 5 1 2 2 0 7 3 1 2 4 2 4 1 4 0 4 6 3 5 1 5 4 2 4 3 7 3 3 8 4 3 6 2 2 2 4 1 4 4 3 5 0 7 2 4 5 1 2 1 1 4 0 7 2 1 2 6 2 4 3 0 8 4 3 2 0 3 1 0 1 1 1 1 3 2 0 2 2 4 1 2 3 8 5 5 3 4 0 2 6 4 4 3 4 6 1 2 0 0 0 3 0 3 6 1 1 3 2 2 2 2 0 3 1 1 0 1 2 2 4 6 4 4 2 0 0 2 5 2 10 0 4 1 1 3 5 6 4 0 3 1 0 9 0 3 4 0 1 3 1 1 2 1 1 1 0 1 2 3 1 2 3 0 2 2 1 4 4 3 1 0 5 2 3 2 9 3 3 0 5 1 4 3 1 1 4 8 0 5 0 1 7 3 3 4 2 2 1 2 8 2 3 0 1 3 1 1 7 3 1 1 5 2 2 3 1 5 0 5 5 5 3 4 2 4 4 1 1 2 6 2 2 0 2 3 4 2 2 4 2 7 6 4 1 0 1 2 1 7 9 0 1 3 4 5 2 1 3 0 4 0 1 0 3 2 2 1 5 0 4 1 0 0 1 4 1 1 0 2 2 1 1 2 3 2 2 0 0 2 0 0 0 0 0 1 2 2 0 3 1 1 0 2 0 
];
B = [
0 0 0
 315302 231898 83404
 783867 612194 171673
 501784 400913 100871
 419598 331872 87726
 371273 294719 76554
 290479 230860 59619
 262208 208765 53443
 254847 204661 50186
 280840 223641 57199
 561751 471854 89897
 363851 305446 58405
 329338 274481 54857
 295204 243285 51919
 275437 226790 48647
 410300 346124 64176
 335221 280158 55063
 355642 302374 53268
 292864 244445 48419
 309606 256564 53042
 392588 330981 61607
 342511 286171 56340
 359114 304227 54887
 346071 291712 54359
 327618 273757 53861
 389262 326835 62427
 334822 280511 54311
 377379 315091 62288
 336760 284639 52121
 354189 297047 57142
 373317 315210 58107
 369701 310857 58844
 356170 298859 57311
 350523 296098 54425
 432194 361268 70926
 363742 308274 55468
 369839 310986 58853
 894150 737751 156399
 350211 296336 53875
 431294 363824 67470
 793059 659263 133796
 418100 352840 65260
 717153 596925 120228
 356187 302476 53711
 421659 356209 65450
 737626 616662 120964
 425469 360341 65128
 710277 592293 117984
 418350 354933 63417
 697182 583608 113574
 426859 363384 63475
 694810 583324 111486
 453294 385545 67749
 701004 589619 111385
 433818 370261 63557
 746166 628589 117577
 656457 553984 102473
 410566 351611 58955
 657140 554281 102859
 307542 266729 40813
 81745257 74943962 6801295
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
19 20 0 0
5 3 0 1
9 5 0 0
21 12 0 0
19 27 0 0
33 22 0 0
49 41 0 2
54 47 1 1
96258 68 4 0
845905 63 10 3
1581463 86 12 5
2719631 126 25 14
4215287 186 255 100
6252935 282 1249 656
7858317 488 1992 1338
8970746 1587 4265 3902
8282053 2949 10528 10460
6093113 6414 19922 20335
3971334 11298 30585 32055
2068085 17971 45051 47481
785980 25915 57495 59397
231445 36792 70858 71811
103012 53664 81764 83779
97806 68858 91696 97717
99845 92300 104073 110610
116354 112195 120421 121509
123352 149321 135191 135381
143672 164569 154430 158234
165845 189021 174417 180667
185009 214213 190006 211549
195032 237295 205727 211391
202361 240471 216040 230089
219853 265092 229762 250840
217126 261491 231758 233996
219847 258232 236128 242557
222231 258913 230374 234200
200570 228901 222678 219467
198556 218747 207319 208082
197964 216333 207158 207513
200601 213406 204444 207703
199876 210810 203937 205346
201549 210280 205977 205742
205491 213457 207914 209789
210724 215523 211755 213548
217943 222079 219302 220539
227603 230954 228601 230070
240807 243118 242080 243031
252411 254614 253420 255732
267553 270818 267692 269096
283271 284896 283318 285328
294802 299162 296635 298372
306461 306276 305666 308259
312244 311507 311070 314269
313936 315813 313254 315804
310580 312334 311336 312277
300469 303095 301805 303877
285961 287845 285702 288901
266103 267849 266284 268254
245172 245807 244190 244800
220919 221943 219204 222679
198630 199044 198475 199653
179029 178951 177957 179218
157055 158943 159127 159865
140535 141650 139763 141382
129198 129471 129878 129222
122278 122671 122815 123300
122040 122110 121116 122259
116405 116842 115807 116266
111050 111440 111777 112030
111402 111412 112123 112308
107915 108483 107714 108714
103199 103453 103142 103561
94868 94499 94200 94638
83393 83747 82819 83741
71436 71397 71703 71493
59599 59662 59004 58716
43211 43482 43089 42863
30240 30196 30310 30919
23755 23932 23829 23850
16503 16617 16422 16189
8668 8960 8871 8823
4077 4132 3981 4184
246 275 251 235
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
