A = [
693874 677410 3126589 614637 587583 574307 570959 572873 562095 543422 534129 521825 514950 505983 498006 491465 483477 476182 468902 462534 458978 453861 449980 444746 434334 405845 401568 392951 367155 364243 361318 360400 359488 356866 355533 353063 353053 350963 350019 350661 347743 347976 348800 345953 345891 344625 344667 343639 342984 341903 341069 341088 340013 339906 338000 338359 337220 336883 337047 336192 335775 335040 334061 334154 335679 336152 337302 336653 340682 345616 362076 364611 372540 387916 390313 390524 389403 389787 386993 385318 384471 384871 381660 381365 379823 377921 377414 374574 375535 372669 372593 370527 369529 367973 367236 365760 363767 364171 361474 360460 358645 357296 356467 355957 354291 352268 350545 350514 348648 347298 346742 345080 344042 342520 340869 339814 338513 336836 336844 334220 333281 331017 330947 329123 329102 327229 326741 324148 323300 322316 321149 319404 318723 316966 315329 314430 313267 312949 311855 309747 309091 307879 305645 305048 303635 301991 302695 300553 298606 296857 296731 294937 293022 293123 292616 291347 289511 288960 287214 285224 285596 283327 281965 281848 280640 279249 277331 276876 275947 274883 273598 273091 273227 271188 270234 268736 266386 265896 264812 263274 262217 261594 258777 259245 258785 257949 256122 254917 254021 253300 252242 250638 250258 248864 248822 247367 246208 243909 244464 242793 241446 240296 240665 238820 238827 236933 235214 234899 233672 232858 231592 230488 229729 228898 228376 227653 226414 225693 224452 222778 221758 221148 220615 219189 220089 218629 216875 216123 215357 214473 214394 212615 211490 209708 209942 209439 207857 207520 206913 204994 204715 204776 203213 202875 201396 199778 199322 198536 197949 197467 196350 195009 194052 192869 193141 192017 190895 188958 188960 187813 187710 186387 186256 184812 184630 183374 182401 181400 181225 180179 178719 178790 177836 177466 177204 175067 175048 173631 173786 173063 172350 171102 170341 169747 169155 168778 167503 166747 166633 165554 164031 163484 162287 162196 161361 161609 159618 159298 157808 158302 156904 156341 155437 154556 154161 153077 153019 152554 151691 150673 150322 149266 148704 148448 147022 146826 145945 145845 144931 144044 143027 142632 141972 141538 140381 139366 139746 138723 137921 137601 136745 136251 135756 134546 134288 133585 132731 131595 131768 131649 130503 129812 128924 128979 127770 127256 127280 126824 125614 125242 125154 123690 123292 122542 122097 121395 121206 120087 119151 118702 118204 117931 117677 116407 117173 115830 115515 114060 114073 114231 113130 112709 111676 111650 110650 110235 110138 109983 108934 108350 107308 107721 106643 105986 105432 105910 105559 104270 104102 103106 102350 102204 101783 101122 100367 99573 99555 99234 98237 98513 97392 97141 96580 95674 95799 95576 95228 93944 93631 92916 93014 92092 91477 91431 90889 90213 90260 89296 88394 87723 88250 87462 86982 86628 85901 85619 84778 84221 84145 84175 83433 82934 82254 81334 81379 80511 80456 79851 79257 79717 78004 78640 77390 77292 76706 76549 75571 76242 75589 74643 73950 73949 73194 72579 72907 73022 71410 70870 71308 70742 70005 69375 69008 68725 68151 67370 67007 66939 66456 65529 65421 64851 64841 64186 63692 63005 63001 62260 61767 61305 60751 60353 60107 59744 59386 59042 58731 57859 57779 57378 56914 56418 56005 55027 54922 54626 54263 53864 53702 53178 52093 52150 51705 51191 51116 50410 50323 49802 49376 48535 48225 48317 47796 46994 46823 46672 46572 46095 45715 45032 45214 44004 43927 43765 42764 43075 42608 42367 42198 41755 41077 40955 40625 39716 39898 39510 38803 39022 38492 38113 37912 37084 36837 36643 36549 36190 35963 35134 35198 34756 34339 34212 33932 33433 32714 32701 32464 32329 31955 31609 31402 30835 30421 30097 29857 30003 29449 29287 28989 28471 28591 28014 27867 27671 27475 27232 26590 26430 26597 26073 25767 25493 25363 24963 24877 24593 24360 24234 24062 23958 23358 23154 22875 22632 22183 22386 22177 21730 21908 21791 21218 20944 20504 20463 20308 20219 19969 19927 19501 19298 18885 18805 18867 18691 18461 18352 18130 17621 17594 17152 17134 17099 16953 16499 16696 16268 16388 15959 15790 15650 15654 15137 15014 14904 14813 14363 14708 14306 14071 14174 13973 13773 13617 13375 13388 13066 13111 12738 12657 12585 12627 12379 12150 11955 11818 11575 11791 11374 11288 11176 11075 10986 10706 10845 10527 10577 10494 10298 10230 9937 9941 9840 9605 9519 9580 9178 9339 9076 9066 9031 8964 8653 8669 8424 8560 8419 8347 8187 7900 7950 7865 7743 7758 7506 7456 7413 7489 7359 7155 7034 7065 6922 6823 6912 6764 6730 6591 6457 6517 6559 6252 6313 6076 6117 6102 5997 5940 5846 5800 5683 5530 5559 5527 5391 5301 5365 5320 5144 5223 5092 5149 5016 4972 4848 4782 4869 4703 4642 4525 4505 4586 4505 4445 4325 4378 4334 4171 4207 4122 4235 4116 3995 3915 3939 3930 4005 3854 3883 3764 3648 3607 3618 3529 3430 3540 3459 3432 3271 3301 3312 3303 3150 3119 3090 3055 3092 3037 3061 2942 2877 2949 2909 2718 2896 2908 2751 2826 2671 2644 2609 2624 2602 2572 2483 2603 2439 2433 2370 2439 2328 2339 2288 2296 2293 2267 2291 2193 2239 2285 2128 2156 2163 2109 2023 2055 2040 2043 2024 1922 1982 1965 1883 1900 1990 1828 1916 1831 1811 1813 1834 1759 1810 1709 1727 1688 1729 1733 1682 1766 1664 1492 1599 1610 1544 1558 1552 1558 1529 1470 1509 1440 1422 1476 1519 1418 1420 1378 1401 1374 1416 1322 1395 1297 1347 1286 1292 1257 1279 1228 1226 1186 1251 1134 1203 1243 1212 1148 1190 1114 1154 1133 1101 1129 1072 1099 1102 1039 1113 1080 1038 1123 1021 1047 1023 1009 1011 1009 996 996 963 908 975 980 999 939 956 926 964 953 887 900 959 867 919 883 895 870 907 882 894 884 887 825 849 874 806 792 775 791 803 769 764 799 786 746 691 798 741 749 744 711 723 685 685 682 691 719 699 689 656 703 694 691 689 691 679 669 674 646 664 639 659 602 630 646 639 619 623 640 607 538 605 555 625 597 578 576 572 564 575 532 538 567 569 564 539 551 538 573 536 534 583 500 558 495 541 558 566 536 539 554 522 492 537 515 508 499 500 536 530 510 494 493 501 488 517 490 511 481 480 431 508 490 481 450 518 445 380 416 448 425 446 444 431 430 402 459 417 415 457 449 422 430 427 403 424 419 414 408 402 418 432 418 410 410 437 390 409 395 375 398 376 384 382 365 368 390 401 407 371 365 386 377 408 353 399 373 375 399 424 390 362 371 308 379 386 352 357 333 384 337 366 370 347 372 360 362 356 344 363 355 302 356 320 341 327 334 318 317 335 327 287 310 330 321 332 324 336 342 312 315 354 298 308 318 344 306 332 324 320 305 294 282 288 315 278 292 260 309 269 266 278 302 296 322 293 279 323 266 291 330 260 274 273 270 269 287 254 264 288 265 281 305 294 306 280 303 289 266 324 304 262 251 278 237 290 270 248 272 261 250 269 256 244 274 260 243 262 265 259 246 250 256 276 264 272 261 222 276 252 231 273 237 239 211 245 244 262 282 253 224 236 221 241 251 216 267 250 207 216 257 220 227 222 225 209 234 241 244 242 229 219 247 222 225 185 210 219 210 244 236 241 250 199 219 232 207 229 216 188 192 198 179 231 207 221 215 221 206 228 195 189 169 215 203 176 190 182 207 219 208 213 205 190 211 202 216 198 188 162 182 174 190 226 190 197 173 187 206 188 159 179 163 146 172 199 181 174 181 165 179 178 175 171 182 202 189 201 182 174 182 195 187 194 194 174 195 197 191 167 187 178 181 189 184 190 193 158 190 180 197 181 200 189 195 178 164 191 156 192 189 185 159 182 171 187 209 171 188 194 185 185 167 184 155 170 175 163 155 176 171 172 162 189 205 178 167 176 187 182 182 161 168 196 179 175 168 166 185 172 178 167 162 170 203 140 166 162 163 148 161 152 174 172 152 155 173 171 165 156 153 168 165 151 163 162 160 151 166 166 149 180 166 160 158 162 139 171 171 163 154 155 152 184 139 151 151 167 155 165 146 160 172 154 157 164 144 155 147 161 127 142 144 120 148 138 158 137 152 148 138 130 150 138 114 145 123 134 119 154 136 108 134 117 133 152 147 127 135 123 143 146 134 132 132 158 149 150 139 131 132 146 127 140 133 138 124 127 138 124 139 133 140 137 112 122 126 128 132 120 119 118 121 147 121 108 108 133 123 108 119 129 109 117 125 122 113 137 121 142 107 128 100 127 115 118 132 134 121 106 111 98 101 111 112 137 109 111 111 111 136 149 129 125 106 122 104 125 137 110 127 106 92 111 131 113 110 104 101 133 116 100 108 110 111 116 118 110 135 107 104 100 111 127 104 134 134 132 128 101 97 118 115 132 112 108 104 124 120 102 108 113 104 123 85 97 120 116 100 96 108 102 121 92 111 89 89 94 99 110 83 101 114 99 102 111 113 102 88 104 100 96 88 104 94 117 111 106 107 95 95 79 97 105 93 78 87 90 96 81 116 95 90 101 82 110 117 99 117 92 93 85 78 94 117 107 122 87 88 100 96 101 83 82 103 73 105 98 93 92 102 105 91 104 108 87 106 93 91 96 82 100 82 72 99 97 87 93 83 78 80 81 69 78 74 89 109 84 79 88 85 85 98 81 106 99 73 86 85 76 80 59 67 80 77 87 71 75 62 75 84 75 75 66 88 63 72 85 66 76 69 84 72 79 65 77 76 75 76 63 64 75 72 65 84 63 74 71 79 66 82 86 76 63 69 71 68 71 51 53 60 60 71 68 71 68 53 63 58 67 58 70 72 60 54 62 65 69 75 74 62 69 69 71 75 51 54 66 56 58 43 64 54 44 84 86 70 70 75 81 66 62 84 56 61 58 64 70 67 68 62 62 70 61 63 59 61 56 65 73 59 59 64 75 65 63 69 61 61 68 63 61 63 62 60 67 74 65 50 61 50 57 60 58 60 59 50 53 52 55 53 68 62 61 48 59 67 49 51 55 50 60 54 62 43 53 46 57 61 56 60 44 51 59 61 58 55 57 59 47 47 56 57 63 56 73 63 42 50 58 55 54 43 52 45 61 57 54 46 48 54 57 49 52 57 41 39 47 66 64 51 51 47 59 60 58 66 51 45 59 57 50 50 64 54 57 51 65 54 58 53 56 51 54 45 53 46 44 43 37 66 45 55 45 42 56 57 50 50 35 46 31 40 50 50 44 54 41 46 47 45 42 48 53 45 47 48 37 37 50 45 60 53 56 56 46 39 57 60 52 53 55 54 48 64 52 38 49 41 40 47 45 47 35 40 48 39 47 42 51 
];
B = [
0 0 0
 70471 33567 36904
 104235 51100 53135
 93562 44671 48891
 73234 36016 37218
 115902 54245 61657
 88721 42082 46639
 126361 64216 62145
 154185 77433 76752
 96294 54292 42002
 355613 173494 182119
 43925 25761 18164
 44516 25380 19136
 27744 15526 12218
 20001 11856 8145
 44441 24212 20229
 10380 6337 4043
 11293 7203 4090
 10635 6728 3907
 15804 10294 5510
 49845 27851 21994
 36769 20990 15779
 25542 16367 9175
 49675 30120 19555
 29815 19769 10046
 68797 43465 25332
 288247 162809 125438
 46782 30448 16334
 56429 36518 19911
 31402 21899 9503
 26952 19552 7400
 60208 38364 21844
 30241 21766 8475
 59509 39036 20473
 33726 24303 9423
 26387 19653 6734
 51855 34903 16952
 44514 31211 13303
 152238 95858 56380
 46646 32704 13942
 32489 24947 7542
 53433 36939 16494
 38314 29722 8592
 48612 34249 14363
 53969 40110 13859
 28632 22875 5757
 60268 42930 17338
 41340 32615 8725
 39478 31983 7495
 77611 55959 21652
 38108 31814 6294
 110598 74966 35632
 60136 47977 12159
 30032 24701 5331
 96227 74458 21769
 39819 33146 6673
 73818 55448 18370
 47522 39337 8185
 38246 32524 5722
 117866 95036 22830
 56220815 50240861 5979954
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
162 475 0 0
37 54 1 1
51 99 0 0
75 118 1 0
83 127 0 0
106 181 0 2
118 232 3 4
235 296 12 9
370 376 15 9
952 572 52 31
1902 803 266 138
3661 1132 657 437
5923 1613 1059 868
8507 2415 1898 1628
11107 3546 3136 2742
17075 5056 5194 4597
35106 7510 8127 7692
127202 10748 12243 11710
686218 14799 18560 18215
2744378 20565 27171 26642
4017440 28768 37277 37472
2038642 39067 49381 49617
495790 51059 62046 62149
130423 64110 75213 75804
104165 79715 90760 89874
123758 97254 106592 106720
144853 117345 126116 125060
161469 137390 144744 145811
183605 157847 166273 166616
203547 180154 187827 188811
229507 202196 209754 209404
264761 222783 230604 230933
287318 244783 251035 251989
307829 264862 271519 271890
298498 285378 290147 290937
313684 303151 306786 308853
326775 318906 323352 322967
341278 333755 336685 336653
352993 347168 349515 349336
362912 359131 361953 362643
372017 371313 372520 371432
381986 379697 383452 381381
390344 388902 388510 389549
394153 395153 395731 395331
396103 395980 395058 396307
395101 393778 394575 394949
382744 383242 382335 381730
361585 362482 362295 361709
338483 339093 339022 338478
309379 309264 309488 309383
275018 275388 274867 274777
242394 241461 242122 242156
213064 211321 211289 212152
184493 185249 185224 184908
165386 165662 165185 165658
152229 151004 151001 150285
139642 139093 140396 139706
131535 131173 131212 130772
127892 128604 127850 127835
128174 127358 127662 127533
134419 135380 133951 134172
139973 139908 139052 139960
136681 137210 137242 137076
132848 132885 132765 132623
124962 124738 125093 125502
113736 113063 113856 113156
98455 97944 99150 97846
81006 81187 81721 81121
63604 63618 63153 63241
42535 42734 42183 41984
20495 20845 20762 20842
4056 4056 3320 3426
0 2 1 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 
];
