A = [
2057366 2244493 36170207 1038835 635033 645034 531001 413081 382286 300523 288301 273994 269513 264908 258576 257867 254012 254794 255472 250493 249867 250958 247844 245631 246820 287199 288600 294947 334621 335934 345285 347998 346691 349756 352790 352548 350704 349956 348138 345115 342537 347511 343917 342249 344394 340281 337061 342808 338261 335181 337556 333011 334541 333546 329836 328153 326484 329207 323751 322133 324841 322560 321473 322456 319953 321131 319368 317376 315291 312943 312418 310729 309378 307742 304820 303968 301496 300316 298757 295353 294717 293768 290611 288300 287964 285733 282415 278807 275896 274351 273405 270811 270522 266897 266833 265112 262129 261491 259395 258250 257836 256112 254001 253532 251685 250871 248905 246619 245883 243004 242124 240042 239541 239500 236888 235787 233355 233151 231940 229551 227744 227326 226046 224726 222948 221376 219742 219706 215991 214410 212895 211496 210852 209544 207446 207109 205281 203262 202708 200663 199091 199221 197037 195893 193831 191927 191282 190326 187875 186603 184881 183126 181693 180305 178266 177633 176051 173297 172747 171471 169718 168793 166186 166117 164650 162484 162030 160229 159154 156455 155529 154544 152283 151525 148911 148054 146628 146008 144441 142873 141518 140090 138856 137387 136886 135549 134375 132703 131464 131588 128793 127564 126014 124860 124572 122958 120841 118250 118328 117497 116066 115358 114377 112739 111107 110228 108449 108988 106968 104751 104435 103486 102455 100674 99607 97931 97027 96127 95089 94273 92302 91551 90001 89388 87224 86385 85231 84891 83795 82871 81528 80991 80761 79553 78119 76905 75823 75541 74970 73515 73541 72366 72127 70037 69490 68372 66953 65884 65777 64766 63371 62308 61770 60221 59926 59505 58308 57235 56294 55635 55015 53805 53118 52498 52065 51228 50585 49552 49122 48377 47323 46797 46156 46001 45541 43956 43936 42829 42763 42048 41700 40467 40232 39272 38939 38032 37760 37034 36579 35856 35293 35221 34553 33899 33029 32504 31841 31634 30874 29902 30136 29189 28607 27886 27634 26696 26392 26015 25739 25407 25062 24627 24335 24036 23571 23031 22534 21924 21732 21394 21177 20694 20409 20031 19807 19320 19077 18795 18527 18082 17629 17452 17417 17313 17180 16949 16612 16061 15873 15863 15351 15333 15167 14789 14474 14386 13935 14383 13356 13522 13196 13140 12547 12561 12183 11875 11831 11576 11267 11272 10785 10795 10622 10279 10149 10057 9838 9531 9466 9116 9228 9082 9010 8899 8564 8661 8319 8160 7989 7864 7845 7510 7450 7321 7152 6855 6923 6750 6776 6560 6150 6453 6246 6138 5845 5688 5705 5421 5523 5532 5498 5319 5239 4945 4956 4706 4477 4613 4512 4335 4375 4281 4133 4077 4001 3829 3980 3880 3745 3551 3608 3681 3393 3452 3338 3414 3302 3122 3094 3050 2975 2966 2938 2776 2787 2550 2571 2540 2641 2510 2407 2320 2338 2484 2351 2353 2194 2163 2160 2139 2090 2042 2164 2175 2141 2024 1907 1989 1963 1839 1891 1708 1802 1765 1827 1687 1739 1702 1613 1584 1500 1601 1445 1475 1421 1468 1436 1456 1443 1366 1252 1385 1268 1217 1308 1185 1287 1186 1117 1177 1145 1151 1166 1078 1036 1107 1032 1015 1037 1038 907 951 907 897 851 869 861 845 871 864 921 770 800 771 780 815 745 739 700 743 748 705 733 743 658 699 662 607 642 613 616 694 623 585 601 618 610 605 584 586 591 623 542 534 513 532 520 560 514 502 535 466 492 600 480 502 486 500 432 486 493 486 490 455 419 474 424 459 465 436 409 374 372 414 401 376 428 408 394 443 387 373 409 369 350 400 368 324 362 352 341 322 347 355 336 269 344 300 315 274 313 293 311 326 297 309 331 339 285 298 296 291 321 295 258 344 248 287 291 298 264 279 284 272 239 261 317 279 307 243 290 271 277 254 254 246 244 234 292 265 234 258 214 239 229 274 261 243 268 273 231 249 286 232 265 229 233 209 215 255 227 218 217 259 212 214 227 225 203 197 221 230 227 209 371 232 189 203 184 201 180 194 201 179 173 169 221 220 200 164 200 189 187 181 194 168 193 168 173 194 182 175 187 192 187 180 175 199 171 205 199 190 169 172 168 168 165 163 166 156 159 164 154 172 155 150 147 142 153 184 164 164 136 167 154 186 123 171 150 166 140 148 126 137 152 152 146 161 150 159 172 136 144 166 156 123 138 119 119 126 175 125 128 139 131 140 124 108 117 128 117 120 117 136 140 156 130 114 137 133 123 124 118 125 119 151 132 138 126 126 116 121 111 139 163 116 119 80 103 140 122 143 113 102 107 122 130 108 119 124 116 98 127 141 130 126 99 111 126 127 122 123 120 143 125 130 112 119 115 119 89 108 119 86 110 94 84 132 97 93 105 94 98 99 82 85 87 82 75 65 101 102 91 117 89 108 109 92 83 85 77 90 72 116 94 68 75 94 94 94 76 78 92 70 79 96 81 100 68 86 78 71 67 72 86 98 71 89 71 83 78 87 88 64 67 76 71 77 68 70 74 70 77 100 85 79 104 70 86 61 65 90 92 81 79 66 74 66 74 67 68 62 71 82 72 80 75 67 71 70 74 55 71 70 98 97 75 78 75 72 49 83 62 67 67 65 70 66 58 63 86 82 81 69 94 62 79 97 81 62 69 76 69 50 59 60 73 53 57 60 50 65 51 62 80 54 53 63 60 65 75 68 43 64 80 55 54 56 54 55 64 58 43 42 56 48 55 39 54 64 51 38 51 61 54 60 63 54 45 45 47 43 53 39 33 41 46 29 49 61 40 42 43 45 39 46 37 70 40 33 56 33 42 43 58 39 40 35 40 54 51 32 41 52 43 40 40 54 35 24 30 38 33 37 34 43 34 33 43 35 35 50 55 36 39 49 26 34 36 27 27 37 31 34 21 32 27 44 32 24 35 45 39 33 35 38 39 54 44 27 45 44 36 46 23 37 25 33 46 28 35 35 29 35 14 29 22 34 30 24 27 28 39 29 31 18 30 22 24 44 23 24 28 38 28 27 29 35 33 27 23 36 25 16 28 26 35 23 27 44 30 25 34 23 20 18 26 35 28 18 21 17 26 32 33 26 25 13 24 35 25 23 30 24 17 19 22 19 23 32 33 25 40 30 24 44 27 10 34 19 14 37 30 27 22 28 23 21 23 18 31 22 26 17 27 15 28 23 28 17 31 28 19 19 20 23 24 23 24 27 21 23 21 19 16 25 33 15 20 27 10 18 13 17 21 15 29 17 27 23 23 29 27 22 17 14 23 35 17 16 25 19 25 9 14 22 19 18 21 16 22 16 20 27 12 25 12 16 24 14 10 16 19 15 14 15 26 18 19 18 17 20 7 27 16 10 15 10 24 19 13 28 19 14 14 16 6 15 17 26 14 20 14 18 15 17 15 23 29 20 23 11 9 23 10 12 11 20 13 13 8 12 14 12 10 19 7 10 21 16 16 12 14 14 11 13 11 11 13 13 9 14 12 17 8 15 15 11 8 13 11 17 20 5 8 8 7 18 9 6 13 11 8 14 6 16 8 9 11 13 7 7 12 15 9 10 26 8 9 19 13 6 13 6 5 13 11 9 13 17 7 10 12 11 13 9 5 10 4 9 14 3 5 12 10 5 7 8 9 6 10 8 10 13 22 10 14 16 12 8 7 8 10 14 2 11 8 5 2 3 9 7 6 12 12 4 9 6 11 5 3 7 3 8 9 6 9 2 11 10 7 8 2 6 3 14 20 10 4 14 3 10 5 8 3 9 10 2 8 7 10 12 9 4 18 6 5 9 7 3 4 5 9 3 12 4 5 6 5 7 4 5 5 2 6 3 5 3 6 4 7 7 10 7 7 7 2 7 2 6 5 4 7 10 5 7 5 11 10 8 15 5 8 11 6 4 4 5 11 7 6 7 5 7 2 11 15 3 8 3 7 8 9 9 8 10 5 13 6 8 2 4 4 11 7 2 7 8 6 14 4 5 1 1 5 4 1 6 6 5 1 4 6 5 7 3 12 1 3 1 4 3 2 2 2 1 3 9 4 3 1 4 8 6 6 6 1 6 0 7 4 1 2 2 6 4 6 2 2 2 0 8 4 2 3 6 3 2 1 3 4 3 4 7 7 4 4 4 5 4 6 2 4 5 3 11 6 2 3 2 2 2 3 3 7 8 5 3 4 5 4 4 4 6 5 6 8 0 10 6 2 2 1 3 2 6 2 4 11 1 5 8 5 3 6 5 4 3 5 6 3 3 9 3 3 2 6 5 9 0 3 6 3 4 3 7 0 2 3 0 2 5 22 1 0 5 2 5 1 2 1 2 3 8 4 0 1 1 1 4 2 2 0 1 3 1 2 2 2 12 1 5 0 2 6 2 5 6 3 0 1 3 1 3 0 6 2 5 2 4 2 0 0 0 3 9 0 2 1 2 2 3 5 2 2 9 2 5 5 0 4 2 4 3 5 0 0 0 7 1 3 5 1 6 4 3 2 1 2 1 0 7 1 1 0 0 1 1 1 6 1 3 4 0 3 0 0 1 3 0 2 2 2 7 0 3 0 1 0 5 1 2 3 1 0 1 4 1 1 6 5 3 2 3 1 0 1 0 2 0 4 3 0 1 1 3 2 4 1 2 0 2 5 1 1 5 2 0 1 2 1 4 1 0 4 3 4 3 4 3 6 1 2 3 3 0 2 2 0 2 4 1 1 1 7 3 3 3 1 1 1 6 2 0 3 1 0 2 0 10 7 0 4 0 5 9 8 3 2 0 1 1 2 7 1 3 0 3 2 2 1 4 1 1 1 0 1 2 4 3 0 2 1 2 3 2 3 2 2 2 5 2 5 0 4 5 1 1 3 1 2 0 2 1 1 2 1 3 2 0 1 2 0 2 0 1 1 0 0 0 2 3 1 1 1 2 0 5 0 1 1 0 0 1 1 2 3 1 5 0 0 1 4 4 0 1 0 2 1 2 2 6 6 0 0 0 1 2 0 1 
];
B = [
0 0 0
 447702 401417 46285
 254764 226816 27948
 530179 480335 49844
 486268 435869 50399
 297865 269161 28704
 609456 555610 53846
 494452 451551 42901
 375919 343931 31988
 754751 678661 76090
 513768 471665 42103
 347474 320433 27041
 1124502 1037106 87396
 253973 234674 19299
 182061 168889 13172
 553316 515383 37933
 170558 155462 15096
 182388 169201 13187
 567894 531616 36278
 29854 27178 2676
 23810 21307 2503
 6428 5782 646
 3317 3097 220
 258610 241014 17596
 909315 849580 59735
 46645 43187 3458
 297989 277449 20540
 958724 898151 60573
 52231 49180 3051
 436474 406263 30211
 1301455 1214734 86721
 91743 86807 4936
 395986 373153 22833
 1079276 1020069 59207
 519311 490975 28336
 353501 340551 12950
 1446546 1374719 71827
 923442 870470 52972
 387907 372899 15008
 1950093 1861945 88148
 854221 805554 48667
 285095 272460 12635
 2696699 2579430 117269
 644543 613801 30742
 213951 204195 9756
 4591702 4415108 176594
 851733 814337 37396
 346457 326591 19866
 7552366 7288388 263978
 1738265 1664900 73365
 34009 32190 1819
 13277012 12798739 478273
 2536333 2438931 97402
 102551 96650 5901
 0 0 0
 3928015 3773427 154588
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
61 193 0 1
13 29 0 0
29 24 0 0
34 36 0 0
29 54 0 0
31 62 260 18
713 102 840 96
13370 60 1104 225
78657 73 1332 260
323019 87 1910 501
789166 97 2311 728
1786249 140 2888 988
3320778 287 3245 1418
5612077 396 3854 1911
7650624 603 4165 2551
9371673 1043 4648 3390
9016504 1434 5147 4246
6542714 2073 5825 5663
3250821 2881 7414 7566
960362 4079 9404 9501
156134 5824 11192 11383
22501 7796 13469 13658
16351 10737 15444 15474
18239 13989 18144 18067
20785 17993 20891 21044
23599 22045 23611 24253
26187 26258 27047 27710
29665 30463 30748 30916
33199 34739 34006 34687
36537 37850 37232 38297
39671 41354 40635 40774
42155 43975 42767 43393
44309 45801 44778 45330
45369 47622 46091 46630
45777 49111 46910 47196
46579 49103 46999 47211
45016 59552 46835 49114
45466 46577 45959 45910
44057 45767 45286 45488
44326 44686 44352 44178
44096 45111 44553 43871
44076 43977 44979 44801
44916 45706 45354 44917
45964 46466 46741 46597
47721 47959 47797 48277
49385 49477 49160 49912
50757 50983 50846 50759
51388 51982 51588 51518
52612 52685 52614 53002
51990 52665 52006 52559
50905 51305 50862 51411
49240 49808 48973 49107
46187 47416 46720 46977
43275 43843 43848 44047
40254 40476 40477 40328
35886 37023 36703 36300
32572 33744 33149 33094
29715 30368 29950 29505
27198 27160 26929 27072
24209 24411 24381 24707
22332 23356 22687 22785
21039 21412 21500 21354
19950 19757 19918 19766
18555 18879 18701 18799
17978 17747 17998 18065
17372 17392 17477 17668
17497 17273 17238 17329
22195 19911 18177 17833
17770 17361 17579 17381
17092 17044 17171 17109
16628 16597 16590 16412
15913 15872 15940 16028
15387 15398 15180 15518
14487 14088 14777 14253
12799 12835 12826 12786
11466 11470 11339 11250
9369 9514 9331 9336
7185 6923 7012 7145
5629 5561 5584 5713
4201 4135 4119 4270
2468 2445 2470 2412
1475 1506 1513 1413
72 88 66 88
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
