A = [
669277 654337 3022128 592804 566914 553848 550840 552795 542186 523962 515135 503470 496809 488278 480586 474125 466297 459326 452350 445891 442581 437389 434129 428832 419060 391462 387399 379149 354402 351527 348755 347986 346998 344498 343254 340761 340757 338518 337987 338322 335729 336068 336849 333979 333803 332484 332541 331757 330958 330092 329377 329342 328379 328373 326375 326872 325783 325411 325650 324648 324387 323732 322817 322737 324357 324642 325746 325274 328799 333356 348773 351028 358541 372935 374968 375257 374089 374284 371792 370289 369437 370131 366776 366375 364926 363085 362608 359821 360808 357902 358147 355696 354845 353392 352770 350921 349507 349625 347088 346100 344147 342991 342240 341924 340013 338096 336277 336108 334554 333066 332756 330980 330103 328596 326783 325852 324830 322986 323274 320615 319866 317654 317418 315738 315781 314026 313496 311134 310048 309134 308068 306683 305887 304241 302537 301710 300667 300112 299079 297228 296487 295549 293273 292859 291474 289868 290436 288558 286504 285121 284906 283314 281453 281652 281188 279885 278312 277671 276025 274173 274474 272216 270927 270961 269823 268358 266423 266171 265263 264239 262893 262477 262607 260662 259969 258593 256114 256002 254763 253184 252159 251521 249057 249323 248906 248160 246433 245203 244390 243777 242933 241153 240968 239457 239545 238074 236974 234590 235135 233618 232295 231175 231651 229975 229946 228215 226662 225900 224887 224221 222903 222005 221097 220281 219753 219373 218129 217288 216109 214476 213582 212927 212410 210917 212057 210824 208958 208216 207450 206527 206595 204772 203752 201937 202205 201707 200274 199940 199337 197531 197232 197507 195944 195571 194264 192642 192098 191430 190974 190463 189444 188224 187174 185875 186342 185358 184364 182240 182491 181326 181210 179967 179845 178463 178322 177077 176060 175187 174928 173915 172563 172472 171590 171264 170860 168940 168841 167523 167773 167065 166343 165351 164511 163788 163405 162935 161687 160800 160828 159698 158436 157883 156644 156615 155857 155918 154003 153796 152299 152870 151467 150965 150009 149195 148861 147623 147804 147289 146458 145524 145103 144141 143581 143405 141990 141793 140906 140801 140002 138983 138076 137677 136995 136646 135640 134559 134926 133959 133184 132952 132160 131487 131124 129921 129718 129059 128134 127153 127356 127191 126132 125523 124471 124599 123428 122940 123016 122499 121320 120959 120875 119480 119200 118276 117889 117362 117178 116150 115138 114770 114151 113882 113718 112519 113332 112096 111676 110193 110217 110448 109140 108904 107928 107887 106849 106544 106353 106231 105185 104648 103765 104202 103211 102434 101937 102370 102072 100750 100678 99657 99060 98780 98429 97881 97103 96294 96276 95955 95109 95375 94146 94053 93391 92502 92526 92467 92089 90772 90670 89883 89908 89114 88414 88393 88019 87348 87301 86387 85513 84893 85360 84597 84182 83862 83102 82821 82034 81429 81375 81349 80820 80239 79584 78745 78808 77953 77949 77294 76791 77117 75490 76055 74804 74877 74271 74184 73038 73779 73070 72153 71600 71486 70934 70215 70520 70588 69144 68681 69066 68567 67880 67289 66886 66541 66112 65346 64965 64876 64443 63443 63440 62855 62874 62220 61743 60995 61141 60391 59952 59441 58872 58488 58301 57941 57546 57158 56884 56165 56046 55570 55209 54692 54198 53330 53155 52924 52511 52100 52059 51479 50398 50516 50086 49551 49388 48769 48734 48207 47819 46976 46657 46829 46273 45522 45302 45209 45133 44609 44269 43666 43787 42565 42543 42368 41312 41686 41270 41012 40845 40441 39815 39668 39410 38460 38680 38275 37564 37787 37332 36915 36768 35958 35794 35517 35460 35089 34883 34089 34153 33627 33325 33230 32923 32459 31729 31755 31560 31411 31019 30746 30492 29925 29562 29212 29075 29123 28608 28454 28150 27620 27729 27179 27093 26891 26741 26472 25740 25616 25834 25313 24988 24689 24627 24251 24136 23814 23625 23501 23321 23234 22636 22417 22154 21956 21486 21673 21496 21053 21239 21111 20522 20325 19834 19799 19668 19557 19311 19296 18905 18639 18235 18181 18264 18107 17877 17759 17583 17028 17029 16565 16574 16554 16393 15946 16137 15760 15894 15425 15281 15135 15116 14648 14531 14407 14371 13903 14242 13845 13635 13728 13510 13351 13171 12977 13008 12654 12697 12305 12232 12179 12233 11935 11743 11602 11426 11194 11385 10998 10917 10760 10686 10585 10335 10456 10148 10177 10089 9936 9885 9574 9634 9492 9256 9167 9290 8857 8996 8776 8745 8693 8624 8333 8328 8130 8232 8078 8023 7867 7606 7694 7576 7465 7454 7229 7144 7118 7185 7098 6875 6756 6800 6663 6515 6611 6502 6449 6327 6178 6272 6271 5983 6052 5853 5873 5856 5728 5696 5608 5571 5449 5296 5337 5288 5171 5089 5165 5106 4935 5006 4883 4935 4813 4758 4640 4577 4673 4481 4449 4307 4296 4364 4315 4222 4119 4166 4106 3969 3996 3927 4029 3921 3814 3724 3729 3704 3796 3673 3697 3592 3466 3437 3420 3353 3231 3374 3262 3269 3092 3138 3152 3168 3005 2970 2935 2913 2961 2870 2890 2805 2720 2795 2758 2602 2748 2742 2607 2687 2513 2523 2489 2478 2476 2431 2350 2430 2310 2305 2247 2293 2208 2212 2146 2156 2171 2139 2161 2068 2088 2118 2002 2033 2043 1973 1887 1943 1920 1925 1906 1834 1873 1831 1768 1789 1856 1707 1786 1702 1676 1686 1711 1647 1676 1590 1598 1576 1631 1614 1564 1640 1557 1398 1513 1512 1453 1452 1438 1459 1405 1364 1399 1346 1331 1366 1412 1325 1331 1266 1286 1277 1314 1200 1304 1201 1242 1166 1158 1173 1185 1130 1130 1088 1150 1047 1113 1138 1111 1060 1091 1031 1073 1049 1037 1032 994 1012 1050 973 1018 992 938 1031 939 941 958 923 910 912 919 910 892 830 885 883 903 862 856 821 886 882 803 826 874 789 837 799 814 790 823 804 816 787 792 737 766 773 729 722 704 726 722 686 697 715 715 670 625 731 672 680 673 653 659 626 621 621 620 659 629 615 595 635 616 628 623 632 613 599 603 587 588 581 588 539 566 578 581 564 564 575 541 500 545 513 564 543 532 529 517 516 517 490 482 524 524 512 488 491 495 519 477 478 526 458 503 448 496 505 517 481 484 486 479 443 482 470 443 452 453 480 470 467 433 434 445 422 447 426 438 418 419 364 451 426 420 385 458 390 338 384 410 379 414 396 390 384 356 419 359 373 412 409 378 385 377 346 377 359 357 334 354 367 385 357 368 360 387 345 360 360 337 351 334 337 346 319 329 348 344 369 336 324 325 334 365 312 350 336 318 361 369 343 324 330 263 334 342 321 310 289 347 291 322 319 314 323 315 322 316 299 315 312 277 319 290 296 295 291 281 294 287 275 264 272 290 298 295 295 302 311 280 285 309 265 274 300 311 277 284 293 293 267 250 255 258 288 251 270 237 273 242 235 256 273 277 289 265 253 289 231 261 285 224 232 232 240 229 247 222 240 243 243 259 275 255 265 259 269 261 236 285 274 232 226 243 207 266 243 225 240 237 226 248 227 226 253 226 221 231 236 218 211 211 223 250 233 247 238 205 239 233 213 252 216 215 191 218 222 247 259 229 199 215 199 219 229 198 245 230 198 203 235 208 211 201 207 191 212 221 211 218 203 194 227 204 198 167 193 204 189 221 210 203 221 181 208 206 184 196 195 169 178 179 159 208 182 206 188 199 190 204 185 172 152 191 177 152 174 158 190 188 191 189 179 168 196 181 204 182 166 149 166 166 171 206 168 176 156 162 186 166 147 166 147 138 160 183 165 159 162 155 159 160 153 162 164 183 166 186 169 154 170 171 167 179 177 159 178 182 174 155 156 156 161 171 166 175 177 142 169 162 182 160 185 174 176 156 148 168 141 172 162 170 134 158 155 163 183 155 171 161 158 160 147 158 131 152 151 136 135 152 147 152 150 165 179 157 141 150 155 159 161 141 144 171 148 153 144 148 156 151 143 146 139 144 164 125 143 138 135 132 142 131 156 150 138 121 154 152 145 139 132 139 139 121 140 141 145 127 141 141 123 146 145 138 133 137 118 142 142 150 132 143 135 164 119 136 138 154 144 146 135 143 157 131 142 148 130 143 136 149 119 131 134 112 134 124 145 121 127 141 123 116 140 131 105 135 107 114 108 146 114 100 124 113 121 130 138 114 123 112 133 133 121 117 117 143 131 137 117 118 114 123 110 126 118 122 109 115 128 118 129 121 133 124 103 115 117 118 127 110 113 114 108 137 113 101 100 125 112 101 108 120 105 111 115 113 103 126 113 127 103 120 93 117 106 111 121 123 116 101 104 92 96 104 92 121 100 101 102 96 127 141 114 116 88 108 89 113 117 101 111 96 82 97 114 92 91 88 84 111 103 87 91 96 100 99 100 98 110 96 86 89 96 106 87 112 111 102 102 78 81 86 92 107 88 80 86 95 95 86 91 88 88 104 71 78 101 95 85 85 88 95 101 74 94 72 79 84 92 92 70 88 102 81 91 92 97 79 75 82 80 85 76 84 73 87 92 75 90 81 72 66 84 90 78 70 74 74 76 67 97 75 71 80 69 87 90 85 90 73 76 74 61 78 96 86 92 68 75 83 85 82 64 57 92 61 81 74 77 76 82 87 74 89 96 74 84 77 76 86 65 81 65 63 83 79 83 79 68 72 71 75 65 74 63 80 91 69 62 74 74 74 86 67 89 83 58 74 71 66 64 51 55 67 61 80 63 62 57 56 68 69 60 55 80 51 67 77 63 68 63 74 66 71 60 70 65 67 67 55 56 64 66 57 76 53 63 59 71 59 69 77 69 57 56 61 60 60 48 49 59 56 63 59 64 63 49 57 51 65 55 63 66 56 50 58 59 63 68 66 62 62 65 64 68 48 52 60 49 52 40 58 50 42 65 68 56 58 52 60 54 49 69 53 53 51 59 64 62 62 57 56 63 57 58 54 55 51 63 68 54 53 58 68 51 51 56 43 55 60 54 50 58 54 57 59 67 61 48 56 46 56 55 57 57 57 48 50 48 52 52 65 61 56 46 57 63 48 42 53 49 59 53 56 42 51 42 51 56 53 59 42 46 57 58 55 50 54 54 43 39 50 52 57 51 69 58 41 47 54 52 50 42 47 40 58 52 53 44 45 50 54 47 47 53 38 37 42 64 64 48 49 45 55 58 56 62 49 43 53 52 47 44 58 49 52 48 59 50 50 48 51 46 51 36 44 45 38 39 31 61 40 51 40 41 50 56 49 45 29 42 27 38 47 49 41 49 40 42 43 44 40 45 52 39 40 44 37 35 45 44 56 49 54 52 45 31 49 55 48 50 50 48 45 58 48 37 42 39 39 43 45 46 32 38 41 39 43 39 50 
];
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
 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 = [
157 458 0 0
34 52 1 1
50 95 0 0
73 116 1 0
79 126 0 0
103 176 0 2
115 228 3 4
223 288 12 9
358 370 15 9
912 557 52 31
1827 787 264 133
3486 1096 643 431
5695 1568 1041 851
8183 2355 1864 1606
10776 3449 3091 2687
16632 4955 5129 4545
34274 7349 7997 7562
124222 10554 12058 11508
671506 14569 18277 17948
2690148 20194 26789 26247
3941905 28272 36777 36935
2001498 38424 48706 48912
486285 50255 61166 61339
127478 63112 74218 74744
101893 78464 89450 88614
121571 95587 105159 105238
142517 115347 124309 123332
158515 135251 142758 143820
180470 155290 163722 164345
200140 177264 185218 186199
225820 198396 206887 206332
259949 219361 227215 227653
282509 240963 247342 248134
302604 260414 267113 267492
293466 280700 285485 286334
308399 298168 301805 303989
321495 313575 318004 317438
335565 327992 331024 330955
346695 341054 342713 342922
356624 353114 354972 355354
365117 364614 365363 363902
374300 372031 375520 373703
382691 381195 380810 381490
386246 387268 387607 386953
387614 387337 386540 387710
386016 384612 385170 385723
373332 373839 373046 372458
352497 353247 353194 352971
329856 330327 329875 329723
301072 300905 300985 301106
267152 267180 267262 266751
234652 233709 234475 234413
206442 204409 204660 205458
178496 179156 178992 178860
159725 159967 159197 160109
147141 146030 146063 145603
135102 134778 135946 135414
127460 126938 127329 126819
123581 124217 124120 124425
124862 123755 123782 123636
131227 132240 130952 131279
136373 136349 135637 136338
133357 133660 133242 133221
128952 129363 128626 128696
121597 121418 121349 121710
110030 109406 110351 109752
94936 94334 95346 94395
78043 77825 77968 77491
59779 59801 59636 59669
39586 39601 39573 39512
17777 17795 17557 17794
2768 2721 2614 2739
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
