A = [
243831 262341 8868142 156638 118071 113253 122549 103661 111565 115004 130133 185537 250068 297118 371018 446844 467198 463155 427245 356495 280134 240114 181836 93111 79425 98285 96338 100910 126958 128679 132095 134891 136683 140533 141247 143515 142303 140919 142199 141234 141774 142274 142509 143830 142875 143420 143270 142149 140548 141141 142204 140108 141018 141611 141226 140093 140367 139813 139914 138158 137994 138133 137288 137443 138241 137321 136447 137101 136294 135111 134729 135482 133856 135150 135369 135069 135117 134653 134460 133887 134170 134637 133595 133470 134175 134678 134440 134048 134456 133062 132208 132303 132687 132011 130702 132343 131439 131091 130957 130547 129898 129088 128546 128833 128795 130111 129289 128727 128766 127254 127319 127362 125759 125848 125356 125384 125579 124868 125855 124198 123482 123843 123667 122317 122998 123340 122198 122810 122209 121490 122064 121705 121240 120106 121205 121071 120572 119911 120064 118759 118659 118273 118181 117610 118161 117413 116977 116798 116475 116906 115922 115416 115498 114381 115126 114616 113507 114723 114671 114551 113936 112451 113067 112230 112012 111210 111080 110959 110498 110896 109318 109283 109205 108549 107737 106887 106886 106721 106160 106505 106299 105930 105190 104966 104729 104081 104488 104245 103925 104949 103143 103544 103280 102687 102809 102621 103674 103112 102597 102068 100554 100612 100646 100016 100108 99020 98812 98723 99046 98918 98443 97362 98172 98034 97571 96941 96458 95542 96085 96163 95594 95663 94367 94057 93492 92953 93461 92729 92887 93163 91996 91745 90935 91536 91378 91226 91108 91324 90717 90171 90462 89143 90054 89250 89815 89728 88598 87826 88430 87713 86965 87004 87372 86780 86327 85570 85314 85071 84859 84744 84611 84042 84198 83303 83243 82812 83395 83189 82367 82306 82203 81669 81402 81031 80702 80459 80668 80165 80741 81044 80185 80617 80313 78861 79317 79397 78640 78598 77690 77874 78050 78400 77234 76970 76802 76548 76403 75252 75430 74604 74738 73673 73846 73532 72990 72440 72450 72130 72073 71795 71781 71043 70776 70813 70177 69562 68682 69613 68448 68864 68877 68134 68661 67546 67991 67858 67317 66547 67018 66745 65694 66547 65771 65325 64674 65016 63957 64084 63685 63690 62754 61860 61742 61454 60732 60499 60899 60402 60079 59511 59304 58466 59092 57974 57636 57714 57637 57422 56799 56387 56267 56052 55690 54959 54960 54700 54473 53938 54381 53792 53619 52937 52642 52565 52604 51992 51862 51186 50907 50544 50166 49926 49665 49393 48383 48419 48280 47900 47150 47369 46733 46923 45484 46006 45668 45409 45544 44552 44113 44021 43853 42814 43054 42526 42076 41899 42001 41118 40572 40882 40401 40080 39363 38938 38510 38389 37748 37526 37220 37032 36485 36297 36245 35577 35319 34973 34167 34563 34232 33751 33373 32850 32614 32544 32081 31862 31650 31147 30584 30174 29873 29892 29415 29018 28908 28586 28599 27703 27829 27660 26862 26678 26788 25941 25907 25329 25581 25044 24647 24128 24611 23974 23852 23294 23365 22923 22147 21948 21579 20836 21172 20434 20503 19970 19515 19188 19259 18916 18566 18481 18147 17869 17432 17500 17258 17292 16809 16471 16473 15970 16049 15693 15384 15087 14889 14434 14581 14508 14240 13971 14056 13409 13530 13105 13297 13183 12551 12879 12943 12400 12317 11710 12239 11830 11689 11315 11408 11277 11281 10990 10621 10285 10173 10320 9944 9829 9079 8738 9426 9253 9278 9078 8689 9003 8644 8352 8326 8138 8206 7158 7061 6908 6940 6676 6560 6229 6371 6118 6258 6121 5855 5846 5769 5784 6151 5579 5387 5523 5037 5624 4759 5286 5126 4983 5532 5278 5120 5664 4818 5170 4834 4961 4868 4444 3827 3742 3722 4712 3908 4512 4177 4176 3940 3876 3900 3709 3687 3788 2884 2871 2887 2680 2699 2651 2554 2508 2575 2542 2401 2501 2321 2326 2319 2244 2115 2124 2101 1968 2003 1970 2013 1936 1956 1813 1815 1714 1802 1788 1758 1632 1697 1636 1573 1506 1513 1513 1515 1539 1570 1585 1447 1489 1381 1443 1379 1387 1419 1356 1200 1190 1173 1218 1210 1154 1210 1266 1171 1283 1309 1253 1255 1089 1120 1113 1192 1166 1101 986 897 982 967 921 940 889 874 869 829 836 798 739 768 864 810 752 772 781 805 762 790 750 767 757 739 783 698 783 777 669 674 650 677 664 601 694 682 717 830 696 818 775 758 740 686 698 687 525 537 536 546 592 502 481 538 504 518 496 505 509 497 483 449 426 477 452 481 463 453 434 471 442 451 408 433 441 482 419 422 460 477 444 414 428 433 396 402 420 395 387 412 380 412 431 366 402 428 412 376 402 359 401 383 370 382 369 348 345 375 339 366 329 360 314 333 335 344 313 339 347 331 318 317 330 335 327 326 333 323 327 330 306 308 281 286 308 326 271 284 338 326 283 306 311 296 304 317 283 293 271 247 270 292 262 249 299 268 311 284 311 276 268 256 303 240 257 254 240 246 246 267 268 249 248 286 251 268 266 269 262 251 245 278 238 274 232 264 250 251 251 234 251 247 261 258 237 251 230 252 250 221 237 205 223 238 212 241 258 216 244 207 233 223 200 214 225 207 243 260 215 215 242 220 232 211 210 244 207 235 207 212 227 212 226 202 240 202 197 183 213 227 203 235 227 222 195 204 224 204 248 209 191 219 237 231 186 172 199 170 197 210 241 209 210 192 167 186 175 192 177 188 174 178 154 185 194 209 189 174 184 163 177 167 182 169 174 181 182 177 190 190 178 172 171 182 198 188 154 188 151 173 142 144 157 192 192 152 175 158 188 180 163 160 164 176 169 166 144 132 133 155 166 152 161 174 162 139 161 170 153 148 165 135 150 137 158 147 145 158 141 145 147 145 128 140 152 141 145 134 134 154 129 156 142 131 145 127 140 157 167 115 151 147 120 132 136 117 129 148 123 117 120 140 135 126 126 116 130 142 118 117 135 112 131 131 123 120 110 102 104 128 126 112 112 116 90 121 94 106 119 115 114 139 133 119 116 119 105 109 127 98 116 117 107 110 110 102 130 109 121 101 109 95 107 123 131 108 113 125 104 109 98 105 103 113 88 89 97 85 122 113 102 91 100 107 96 94 115 101 107 102 113 103 103 93 99 90 103 119 87 114 82 85 90 92 101 111 98 91 110 90 102 115 107 100 87 87 89 93 100 74 88 109 88 109 83 92 86 95 82 91 85 88 81 89 90 83 97 96 88 83 81 74 78 85 93 100 75 80 96 106 97 68 97 89 75 82 75 93 65 75 82 87 84 86 102 76 83 84 96 79 93 69 81 103 74 80 88 86 83 76 87 70 76 81 63 76 64 75 68 67 64 60 81 102 60 84 74 97 86 65 84 77 106 88 57 76 70 65 93 101 69 90 65 92 89 81 80 80 67 65 91 76 78 74 69 56 73 82 47 80 72 79 72 69 55 68 89 59 60 68 59 57 52 49 71 70 65 63 58 51 68 75 61 59 72 61 58 47 60 71 47 70 56 59 53 54 42 61 64 58 56 72 52 75 43 74 66 53 54 61 46 49 55 55 66 48 53 52 65 59 47 48 54 35 41 62 49 53 59 43 54 48 39 47 44 55 42 44 61 50 39 42 36 61 43 54 54 38 45 50 31 42 47 43 44 33 40 43 34 36 40 40 42 37 36 38 45 35 35 38 37 46 41 45 39 43 36 47 37 39 53 46 37 42 46 46 34 35 34 42 40 42 45 41 46 42 43 56 45 40 47 48 51 33 31 46 44 44 51 42 36 44 50 48 33 40 49 43 46 32 54 57 52 48 39 35 53 35 32 45 40 47 34 44 44 43 33 39 30 33 49 36 39 43 41 48 28 33 30 37 43 38 34 32 33 42 28 49 39 32 32 33 26 31 34 31 26 39 41 40 28 38 34 33 39 36 30 36 37 31 30 50 35 33 33 28 30 36 28 36 45 27 35 39 27 34 39 21 30 35 29 34 37 47 36 27 29 27 27 36 26 35 24 42 32 24 33 31 24 34 25 31 19 32 27 27 20 16 31 38 29 26 33 36 32 36 23 30 24 24 21 30 36 33 26 24 29 31 29 17 25 31 28 26 17 26 25 31 30 25 25 32 23 28 25 36 36 23 21 25 28 27 24 26 25 14 27 25 21 34 34 17 29 19 25 36 29 33 38 17 23 33 28 23 28 30 16 23 23 31 18 20 17 25 23 21 15 21 15 22 28 26 23 16 17 26 14 26 21 18 18 19 24 23 28 21 20 37 20 31 23 13 16 27 11 27 29 19 38 22 15 15 21 22 22 24 16 21 18 17 16 19 10 24 17 16 21 15 16 21 18 21 16 20 25 22 21 19 18 16 28 20 26 20 19 22 17 23 14 19 20 19 17 14 36 18 14 23 19 16 16 19 19 23 22 24 26 8 17 13 16 14 23 15 23 18 16 23 17 21 17 12 22 20 19 16 11 17 16 16 20 14 11 15 19 20 16 12 20 16 15 20 14 19 16 15 23 16 21 16 19 24 11 23 19 18 16 20 21 24 23 9 19 22 21 17 17 18 16 28 20 19 21 36 13 22 17 13 17 16 18 13 14 23 14 21 19 20 19 17 17 10 24 21 12 16 24 13 18 20 14 13 18 15 20 15 15 17 16 19 10 15 17 10 14 14 18 20 18 15 21 16 13 15 13 14 21 16 12 23 12 14 14 9 9 12 15 19 21 11 10 12 19 15 16 17 5 14 14 33 28 18 13 16 13 17 9 15 13 15 16 11 23 14 13 16 15 6 11 18 11 14 13 17 17 8 15 8 15 8 6 11 17 11 9 8 16 16 7 10 12 10 18 9 17 10 16 12 16 17 14 16 16 12 13 13 17 16 11 11 5 13 14 13 16 7 9 7 12 14 12 12 11 11 13 9 12 7 8 11 13 8 9 12 12 15 9 12 7 9 12 12 7 8 14 7 10 13 11 12 12 9 8 9 5 9 9 8 7 8 14 11 12 9 10 12 11 9 12 11 16 7 10 16 7 12 12 10 5 3 8 10 9 9 19 10 10 5 7 8 10 8 9 22 8 6 9 5 14 9 8 11 11 13 14 11 8 9 15 16 8 13 8 15 11 6 12 9 7 4 12 
];
B = [
0 0 0
 47688 35250 12438
 39095 27601 11494
 40429 28199 12230
 48200 32170 16030
 41972 28413 13559
 39999 29435 10564
 42246 29976 12270
 49878 37242 12636
 38730 29046 9684
 35981 26391 9590
 41266 31142 10124
 40684 31231 9453
 64792 49487 15305
 17455 12204 5251
 121912 93824 28088
 22622 15948 6674
 19889 13420 6469
 29264 22832 6432
 22270 16413 5857
 21531 16731 4800
 19990 16087 3903
 40113 31425 8688
 19074 14587 4487
 27153 21646 5507
 45442 36284 9158
 10070 8880 1190
 87909 71173 16736
 72128 62895 9233
 10512 9410 1102
 13151 11839 1312
 23570 21750 1820
 35112 28802 6310
 33634 30001 3633
 30334 28538 1796
 113962 91269 22693
 13263 11992 1271
 35192 33055 2137
 8481 7968 513
 56026 48313 7713
 7210 6755 455
 33111 31487 1624
 42720 36375 6345
 6861 6458 403
 150734 143611 7123
 15083 14233 850
 41911 36028 5883
 11675 10966 709
 92476 84789 7687
 26449 24830 1619
 42281 36548 5733
 67708 64289 3419
 11116 10332 784
 79334 68799 10535
 78347 71390 6957
 56730 53617 3113
 15433 14446 987
 46316 41205 5111
 13704 12974 730
 109114 104753 4361
 27772321 26369275 1403046
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
21 197 3 18
11 28 0 4
8 34 3 4
26 48 1 18
33 35 3 13
20 54 52 57
107 91 164 182
169 70 211 410
240 112 341 883
308 155 642 1914
335 188 932 3470
511 228 1664 6667
710 313 2803 12366
1263 478 5043 21823
3697 707 8566 34496
28507 1089 15116 52352
272308 1795 23073 68848
1515028 2748 28206 68587
4284933 4078 23934 47465
4570814 6112 14971 21540
1426148 8551 13458 13871
137213 11612 16339 16542
28930 16047 20229 20289
27844 21215 25127 24686
34181 26800 30218 30091
40520 33313 35976 35989
47020 40472 42230 43102
54445 48866 50719 50650
62616 57582 58867 59009
72267 67112 68246 69096
84583 76753 78172 78611
97057 86367 89328 88718
113444 96692 98961 99207
117931 107391 109501 108809
121178 117045 118103 118146
128528 125831 126543 127609
136009 132657 133856 134711
140359 141086 139848 139407
144629 143857 143966 144656
148377 146905 147432 147750
148565 148458 147995 147604
148108 147430 147211 147798
145458 146259 145491 145736
142615 143378 142324 142532
138138 138198 138318 138442
131674 132828 131911 131870
126540 126391 123523 123468
112817 113242 113476 112792
102433 103055 102303 102915
91944 92243 92515 93226
84799 84614 84181 83503
74320 73868 73656 73983
67989 68401 68360 68241
63934 64779 65251 65051
60647 61043 61421 61615
57589 57487 57320 58015
55900 56277 55916 56300
54377 54719 54682 54413
56448 56388 55161 54976
55164 54706 55584 56040
55642 56733 55408 55209
57689 56388 55532 55794
57201 57471 61498 60904
55702 55796 54840 55149
53303 51897 52421 51550
45396 44931 45431 46153
37295 37450 40502 39400
30114 30029 33623 33920
28378 28477 24594 24604
16542 16656 20830 19940
13909 14401 9780 9498
7968 7153 1341 1288
0 1 0 1
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
