A = [
220584 217074 1033225 214061 206709 200254 203714 204061 207498 205639 222203 243589 268449 306889 345097 376118 398021 409090 411755 404154 392022 388343 382482 381264 382025 441663 444157 438797 489440 420738 420960 416027 350825 357087 350183 351227 346910 337984 338935 334792 336335 336359 335448 338026 335194 333206 333165 329809 328086 326609 326489 324815 326932 324937 324920 325739 324043 321928 320866 317652 316908 316715 315683 316769 315889 315346 314334 312327 310851 308181 306744 306015 304678 303551 303974 303025 300997 300243 297084 295014 294126 291406 289936 289704 288849 287917 286094 284330 283556 280968 278993 277392 276601 275679 274175 273436 272058 272406 270350 270173 268341 267249 266495 264029 263746 262588 261493 260718 260005 255831 254483 254518 252442 250801 249193 247826 246738 245686 244717 242446 241846 240500 238507 236835 235837 234812 233286 231783 230487 229574 228129 227342 223971 223668 222218 220788 219843 218954 218170 216720 214878 213211 210791 209712 208682 207344 206059 204628 204355 202484 201609 199931 199045 197656 196739 194674 193825 192659 191309 190232 188436 187938 186269 184683 183736 181967 180799 179392 178792 177578 176905 175173 173341 172294 171225 169947 167865 167439 165924 164342 163881 161916 160917 160282 159606 157837 157289 155618 153212 153275 152433 151265 149715 148969 147143 146341 144568 142998 142467 141574 140147 138693 138135 137535 136394 135120 133484 132429 131500 130027 129018 127118 127085 125553 124769 123997 121725 121350 120101 118483 117417 116708 116211 114658 113604 112971 111830 110222 109117 107698 106907 105171 104932 103881 102793 101678 100480 99539 98060 97558 96211 94967 93409 93314 91884 91866 90220 89155 88381 86298 86205 84394 84014 83237 81466 80820 79667 78865 78171 76732 75412 73874 73497 72749 71861 70995 70651 69048 67910 66926 66292 65517 64055 63691 62302 61504 60781 60220 59446 58567 57508 57063 56136 55384 54453 53417 53447 51855 50816 50717 49399 48695 48085 47344 46646 45929 44847 44763 43684 42999 41974 41412 41250 39927 39523 38909 38072 37566 36573 36426 35756 34884 34557 34089 33311 32885 31779 31568 31047 30631 30188 29319 29050 28483 28046 27292 27062 26323 26249 25500 25237 24445 24061 23742 23476 23095 22454 21747 21512 21216 20933 20560 20325 19559 19333 19024 18740 18037 17967 17652 17130 16938 16691 16200 15992 15858 15365 15122 15055 14897 14192 13930 13649 13431 13057 12946 12795 12414 12205 11835 11854 11608 11476 11196 10984 10766 10592 10436 10076 10076 9630 9500 9410 9240 9211 8908 8711 8763 8456 8428 8136 7957 7942 7948 7790 7514 7201 7234 7118 7039 6927 6748 6556 6549 6304 6256 6149 5976 5993 5881 5746 5668 5495 5501 5454 5300 5247 5056 5118 5072 4883 4836 4666 4559 4546 4511 4325 4386 4340 4353 4342 4333 4141 4048 4037 3946 3898 3875 3853 3744 3748 3653 3605 3590 3583 3355 3437 3424 3341 3341 3248 3271 3182 3107 3052 3072 3004 2982 2962 2968 2961 2800 2854 2775 2777 2804 2723 2643 2668 2628 2554 2510 2451 2551 2514 2509 2416 2579 2380 2409 2379 2362 2347 2355 2273 2216 2245 2216 2145 2123 2128 2137 2111 2162 2135 2081 2071 2058 2104 1955 2029 1847 1946 2028 1994 1894 1865 1851 1852 1840 1869 1839 1858 1756 1804 1754 1758 1736 1795 1727 1725 1628 1659 1717 1634 1678 1652 1652 1606 1618 1487 1581 1545 1591 1534 1526 1505 1459 1531 1503 1476 1532 1432 1493 1416 1386 1387 1407 1388 1359 1398 1400 1367 1395 1329 1344 1289 1347 1367 1314 1355 1316 1274 1323 1246 1259 1290 1279 1262 1281 1277 1255 1249 1239 1207 1150 1200 1128 1147 1203 1172 1152 1164 1118 1100 1140 1111 1104 1094 1179 1116 1100 1120 1128 1120 1117 1056 1031 1054 1028 1057 1017 1039 1091 1009 1007 1004 1020 968 878 924 1010 939 959 956 965 989 950 983 925 947 934 925 946 924 901 895 929 900 881 921 877 882 911 883 849 872 903 910 853 785 875 796 845 893 821 840 805 793 889 804 852 821 828 831 780 797 778 738 825 830 794 737 767 700 708 756 702 739 734 760 689 733 729 653 718 701 714 693 667 706 706 651 675 665 653 638 693 641 646 639 635 607 671 634 634 582 627 619 597 594 651 596 623 588 570 618 601 537 649 585 588 562 588 619 550 564 586 573 604 582 638 542 587 540 590 535 511 530 576 552 566 507 515 509 560 541 515 510 522 474 508 557 528 481 476 503 521 478 468 484 510 470 524 469 490 483 466 488 463 471 471 444 438 466 457 490 482 428 417 417 421 439 413 416 440 464 403 413 418 387 436 454 395 447 400 387 384 394 423 393 445 365 425 390 391 390 373 406 365 391 384 384 393 347 386 395 359 383 364 344 349 376 350 367 383 364 360 353 358 327 328 351 322 391 334 376 368 333 316 356 339 315 327 342 323 329 315 344 331 307 289 301 333 328 312 338 339 320 295 296 273 300 279 306 308 304 304 306 291 288 277 304 303 262 278 293 292 305 265 274 286 263 268 265 244 266 282 266 241 265 285 278 278 262 252 272 278 251 284 275 276 237 247 247 247 271 240 237 259 254 256 254 240 241 246 239 245 240 258 271 241 220 232 234 222 224 236 234 218 229 214 215 206 223 210 241 243 212 230 215 189 227 176 198 202 220 226 210 201 184 221 191 187 203 210 191 175 180 232 209 213 197 186 167 190 172 204 155 172 201 191 177 184 191 191 171 201 193 172 172 161 165 180 175 187 164 174 193 163 191 178 173 160 168 179 155 156 175 162 162 165 156 176 157 159 187 155 152 143 162 159 154 170 159 144 148 157 145 163 138 155 121 165 151 158 136 144 123 132 136 129 150 127 152 151 134 131 145 136 126 125 151 145 124 140 141 138 143 130 139 148 137 123 128 120 129 126 127 113 118 120 132 131 112 117 114 101 138 109 114 107 122 107 108 126 120 135 110 118 118 115 114 104 113 114 96 96 129 132 140 111 112 120 103 98 94 101 107 110 111 96 92 100 89 106 105 87 95 98 88 81 108 83 102 97 85 115 87 94 96 77 102 94 98 88 82 95 83 92 102 99 92 96 81 91 93 83 74 77 85 69 80 94 93 84 89 84 70 84 82 88 92 89 78 95 89 74 90 62 81 72 77 67 67 81 82 63 68 70 91 85 80 65 67 63 68 84 73 81 52 86 71 65 61 74 70 62 74 85 85 60 63 60 55 79 71 74 64 72 70 72 71 51 75 73 54 72 60 77 70 69 58 54 69 50 57 58 50 61 57 51 61 68 65 74 74 62 64 59 51 48 45 56 54 61 54 53 61 54 55 33 67 60 63 49 53 50 49 55 54 51 57 52 51 60 46 57 50 51 47 46 41 47 47 62 41 60 47 51 53 44 49 48 46 42 31 50 45 53 44 45 45 47 45 61 45 41 49 40 45 51 48 48 54 43 41 57 52 52 37 42 41 43 36 44 44 42 36 40 42 37 35 33 44 47 39 39 34 35 44 58 46 37 47 39 37 43 44 38 41 42 32 41 44 42 32 26 41 37 42 42 32 40 39 31 41 31 30 35 30 32 34 38 33 31 31 24 27 36 41 26 31 38 40 35 44 23 27 17 38 41 25 34 30 33 39 26 29 38 26 32 31 34 37 31 29 18 22 28 27 23 31 21 28 27 28 23 30 35 33 24 29 33 31 25 30 32 37 27 29 21 26 25 28 19 22 25 22 21 26 21 19 20 28 26 29 23 24 23 31 22 18 21 21 21 20 21 22 33 23 23 22 29 20 23 18 24 35 19 25 19 31 25 19 21 24 19 17 24 26 17 24 17 22 26 19 25 19 10 24 32 22 23 14 23 13 20 21 20 24 12 16 10 20 22 19 22 20 21 13 20 18 13 18 23 20 17 26 22 15 19 21 17 18 21 18 11 21 17 24 18 17 13 21 22 12 13 16 19 17 11 16 20 16 18 15 13 13 10 12 19 22 10 20 15 8 21 19 29 14 18 14 10 15 18 16 17 10 22 12 17 9 17 21 11 14 9 9 12 14 16 14 11 7 12 9 14 12 13 11 12 17 8 17 14 14 16 13 11 12 5 20 8 18 18 8 12 11 5 15 11 19 9 19 15 10 9 5 14 6 15 6 15 8 9 5 13 18 15 8 12 8 13 9 14 11 12 10 12 15 6 16 7 12 9 8 8 10 11 12 8 6 13 11 14 6 11 11 8 14 14 11 10 14 6 12 9 5 6 7 10 7 11 13 10 10 8 14 10 10 9 9 13 8 10 10 11 12 14 3 14 8 6 8 7 14 7 8 12 15 9 9 9 7 9 8 11 6 11 8 7 6 5 10 10 8 14 6 11 2 7 3 5 7 12 6 6 7 13 6 7 8 14 5 6 6 8 10 7 6 5 5 6 4 4 8 3 4 5 7 3 3 9 6 7 7 6 5 5 6 9 7 3 11 4 10 7 6 4 7 7 7 6 1 12 3 5 3 1 11 5 6 5 6 4 7 6 9 6 5 6 4 4 3 3 2 7 1 2 4 6 1 6 2 6 2 3 3 4 3 3 7 5 6 7 4 1 6 2 4 4 5 6 5 3 2 5 5 6 4 3 7 4 5 6 5 8 3 4 3 4 3 6 4 4 3 5 4 3 10 5 1 3 1 5 6 6 1 7 2 6 4 4 4 5 3 7 4 6 1 1 3 3 3 3 7 4 4 4 1 3 6 1 4 1 5 3 11 4 3 5 4 3 1 1 7 0 2 5 5 4 3 2 5 3 1 1 2 2 2 3 3 2 4 0 2 2 4 4 4 3 2 3 5 4 4 7 1 3 5 1 4 3 3 5 4 5 0 1 2 1 3 4 3 2 5 5 2 5 5 4 4 2 0 1 2 1 4 1 2 3 3 2 3 5 2 0 1 1 2 2 3 2 2 2 2 3 1 3 2 2 2 3 3 1 1 3 4 2 0 3 1 1 1 2 3 5 2 1 2 1 1 0 1 2 1 2 4 1 2 2 5 0 1 2 1 1 1 1 5 1 1 2 2 2 2 6 2 0 
];
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
 131347 109965 21382
 177239 149377 27862
 180211 152254 27957
 146223 122929 23294
 198254 167637 30617
 150156 126544 23612
 219647 186123 33524
 307892 259336 48556
 193662 164202 29460
 194087 164355 29732
 324701 274920 49781
 231414 196856 34558
 276194 234156 42038
 203584 173538 30046
 197311 167720 29591
 340394 289413 50981
 204278 174464 29814
 325537 277322 48215
 220772 188368 32404
 327502 279484 48018
 257571 220284 37287
 303820 259328 44492
 279953 240584 39369
 314489 269169 45320
 278006 238589 39417
 329330 282514 46816
 371824 319402 52422
 224979 193760 31219
 370733 319061 51672
 238331 204271 34060
 25069113 21623310 3445803
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
4 18 7 2
0 6 0 1
1 7 0 0
3 11 1 0
4 11 1 0
3 10 0 0
20 19 11 2
113 40 55 7
1533 29 100 31
7490 56 217 73
16195 62 285 138
31426 105 472 238
58283 153 841 496
117128 226 1344 965
247501 400 2022 1620
625701 737 3205 2817
1462034 1419 4758 4701
1953899 2581 7588 7363
1107564 4570 11596 11496
263309 7064 15770 15889
61013 10251 20507 20623
39793 14824 26073 25727
38154 21503 31485 31948
42518 29696 38274 38713
49587 39091 45806 45855
58567 49088 54427 54607
67339 59209 63340 63339
75901 68920 72770 73225
85133 78149 81579 81225
92128 85946 88570 88856
98634 92746 94935 95285
102583 97102 98744 98716
106586 99646 101499 101886
105299 102395 103184 103606
105637 104051 104384 104464
106457 104005 104905 104528
106133 105106 105519 105645
107440 105326 105880 106569
107997 107256 107748 107785
109771 108651 109495 109458
112238 110973 112176 111553
114905 114313 115127 115036
119235 118814 118702 119067
123640 123166 123649 123500
128563 128285 127960 127992
132789 132766 132867 132426
138152 137071 137074 137354
140266 140434 140631 141479
142998 143437 142862 143480
143236 142701 143024 143021
142157 141504 141383 141778
138045 138607 139063 138633
133406 133197 133391 133466
126668 126368 125950 126854
118963 118913 118140 118973
109793 109527 109132 109592
100003 100403 99970 100791
92097 91798 91534 92093
82187 82672 83034 82718
75681 75750 75620 75632
68693 69380 68725 69024
64330 64363 64454 64587
61062 61221 61324 60950
58482 58593 58424 58141
58778 58476 58625 58792
61554 61409 61186 61612
65416 65670 65500 65412
70614 70963 70577 71000
78496 78684 79066 78860
87941 88302 88343 88342
100911 101497 100429 100361
107639 107583 107002 107585
114674 113661 114116 113790
117999 118300 117577 118141
115618 115470 115852 116249
104531 104740 104564 104185
86147 87024 86224 86631
59627 59480 59673 59511
30332 30352 30514 30232
10513 10529 10493 10537
1611 1596 1587 1633
10 7 9 8
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
