A = [
1003874 1034086 22327046 1360531 465005 459569 453325 293281 288689 277605 274541 272777 267847 275103 256179 266611 249228 247985 242142 240375 235804 261422 261259 258599 252599 258509 253069 245613 259909 259568 265360 268117 266332 259020 251715 266457 257048 253863 258331 260025 260971 258479 264276 254823 273416 269354 236310 238146 257133 259549 253934 248309 240025 230849 223332 219611 246162 253247 256478 244916 240371 231400 224726 231047 220416 213135 210389 207669 205504 207749 206377 208940 223618 213270 208334 210107 219877 219612 205214 202045 197954 203896 212007 203472 209918 196440 197560 201308 201383 198444 193226 180765 189613 191745 195696 186810 174706 184643 171149 174546 182358 183920 177723 188031 180720 176389 188062 185508 176583 190738 181031 184354 177329 179400 170648 179070 173059 176019 183898 172770 156226 166863 166512 166345 166021 167363 165528 170505 174528 172885 160079 167994 160603 171055 160290 163329 169301 165678 168075 163821 168538 160881 155528 156979 165032 156206 153407 158305 154699 166622 146313 146670 147609 148292 145219 146343 140745 140382 135378 134008 135836 134026 128982 131546 132600 130063 136562 137418 136183 132639 131004 130958 126122 127985 127577 124952 125931 122755 123371 125795 118414 121677 125111 125362 118712 118147 111961 113633 109612 116939 108377 110018 105948 106328 109198 110183 103229 106264 105401 101341 99942 101144 98978 98274 97644 100441 98435 99555 94646 89824 91472 89232 89534 88008 86098 84941 83103 82633 82470 85032 80264 79636 78351 77873 74373 71524 71009 69777 70080 68500 68070 67953 65433 65696 64241 64969 63005 62066 62647 63109 59423 58351 57792 56835 55728 55432 55475 55222 54100 51098 51794 51268 51597 49371 48894 48177 46154 48151 44822 44690 45387 44613 42587 42543 44440 41350 41372 41411 40049 39240 38303 37196 37296 36026 35836 35820 34800 34932 33886 33301 32240 32739 34981 30464 30100 30329 28825 28180 28304 27889 27762 26749 26637 27386 26819 26422 25289 24573 23962 23589 24158 23235 22642 22113 20891 20402 20069 19486 19473 19222 19780 18860 18206 17072 16379 16915 17592 16495 15753 16485 15749 15381 16162 15588 14798 14872 14573 14102 14151 13376 12876 13312 12982 12945 12763 12194 11939 11909 11603 11490 12017 11286 11412 10885 10574 10402 10198 10239 9696 9768 9679 9487 9287 9492 9338 8492 8855 8722 8405 9071 8151 7958 8335 8483 7363 7469 7593 7480 6916 6850 7049 6680 6465 6724 6544 6426 6210 6313 6329 6226 6039 5832 5726 5647 5578 5285 5162 5055 5311 4976 4691 4674 4603 4521 4201 3943 3792 3948 3871 3723 3835 3694 3535 3629 3442 3437 3354 3245 3216 3118 2912 3244 2952 2935 3064 2656 2740 2703 2599 2644 2528 2348 2464 2167 2167 2171 2205 2146 2233 2067 1991 1942 1956 1940 1843 1939 1732 1842 1738 1763 1535 1569 1865 1471 1471 1428 1371 1412 1479 1449 1349 1379 1366 1266 1297 1309 1293 1329 1171 1146 1226 1180 1188 1223 1082 980 1106 1017 1026 1075 990 1032 943 1011 897 893 931 945 989 842 846 825 918 915 746 854 734 768 658 514 468 472 418 526 453 434 472 447 438 431 419 415 387 425 371 379 377 381 359 335 313 304 308 287 240 285 266 286 292 267 285 254 289 279 277 257 299 276 235 236 243 237 310 314 323 302 315 273 275 257 321 275 283 278 287 301 258 233 249 267 274 270 254 286 276 264 241 204 235 248 269 238 268 259 263 239 232 281 234 264 405 282 242 220 245 252 279 342 273 266 346 282 295 277 258 284 269 224 227 240 288 277 256 224 243 361 290 223 276 218 210 244 214 179 194 178 147 152 154 171 197 204 161 167 152 144 151 171 177 106 113 101 116 119 195 217 193 174 155 184 174 151 159 91 118 113 97 121 120 104 125 106 107 112 123 131 148 138 175 154 165 147 185 181 162 184 179 174 138 137 147 140 206 168 199 273 270 278 295 296 277 345 315 331 339 347 319 306 346 334 392 413 429 498 484 537 407 322 288 353 336 380 306 326 395 348 341 377 296 285 325 280 262 179 241 229 190 203 193 199 197 203 181 214 183 190 158 136 134 127 109 117 106 99 119 122 85 120 120 126 120 125 136 171 235 167 184 197 215 207 259 316 358 300 362 371 362 344 401 477 456 457 500 474 473 509 451 567 549 543 565 448 426 434 407 395 314 339 340 362 386 389 339 282 320 344 288 253 293 275 361 275 288 289 256 335 290 282 236 280 297 281 263 255 267 279 299 249 199 202 268 259 266 218 214 249 251 200 219 221 271 223 235 191 140 152 149 155 174 186 187 172 185 197 212 182 199 186 221 222 241 201 278 288 300 275 319 295 289 245 296 270 232 264 287 232 237 214 265 294 251 311 277 279 343 309 309 291 263 322 370 427 368 418 352 373 389 368 370 370 369 340 302 268 318 300 285 300 297 281 334 301 323 274 296 273 288 258 244 261 263 229 235 285 385 317 334 312 332 393 344 313 258 282 321 306 306 294 388 395 434 382 345 374 419 437 419 419 417 546 466 439 438 404 514 544 499 451 448 507 552 498 429 321 373 579 485 516 499 504 473 513 409 477 396 477 494 655 592 628 608 551 610 533 611 560 535 630 525 567 517 583 619 652 528 529 627 580 588 664 692 777 712 707 668 691 577 672 748 662 634 475 430 373 505 494 371 417 461 450 452 355 424 486 420 520 420 493 419 398 383 357 427 457 505 501 470 431 362 375 441 467 417 412 418 450 339 361 357 441 478 358 393 388 342 356 334 329 335 344 362 319 298 265 316 339 270 319 252 269 220 184 158 201 188 189 187 143 155 131 134 166 134 162 155 175 100 87 114 121 86 110 90 91 68 109 94 77 86 122 141 154 119 193 219 147 147 203 289 434 358 345 298 422 396 360 333 374 352 350 377 266 280 262 299 345 289 321 332 278 331 290 329 406 349 323 364 291 203 87 87 79 110 99 82 87 78 102 112 100 85 80 53 60 97 76 73 62 77 113 124 142 178 201 205 328 284 290 332 355 277 260 294 255 276 371 367 340 282 330 328 290 334 234 273 364 344 870 294 302 443 454 372 369 400 478 389 426 424 374 371 354 285 133 112 101 103 117 109 115 112 133 99 125 190 84 133 114 81 109 98 132 108 140 140 134 101 148 148 122 116 92 108 110 113 153 204 187 270 220 287 214 236 292 311 282 216 277 288 287 242 275 217 293 258 270 242 213 282 294 254 263 246 260 303 329 322 305 370 365 402 378 363 351 358 344 284 306 269 279 261 270 236 224 243 230 143 182 151 190 201 177 155 171 213 191 157 161 151 184 198 197 178 160 205 191 178 163 82 75 80 76 74 75 75 60 55 66 63 59 92 84 84 92 94 64 78 86 174 157 222 163 157 150 216 204 185 172 198 240 185 206 173 174 178 156 175 150 146 191 154 154 132 240 255 242 282 354 314 284 287 330 340 243 218 206 236 287 410 366 257 196 267 218 191 215 195 201 220 226 177 213 185 56 75 191 74 60 61 74 72 55 45 47 68 53 65 61 58 48 75 75 109 194 201 212 213 189 258 214 210 215 228 242 161 144 180 186 139 177 181 156 184 153 168 152 167 171 190 225 121 158 182 165 161 187 217 199 42 77 33 40 121 161 186 142 108 39 38 37 39 35 30 43 123 111 107 99 129 100 111 111 114 114 26 36 33 29 16 20 12 23 24 23 25 13 24 29 25 32 31 31 24 38 26 29 39 34 37 42 32 26 31 22 38 25 37 34 41 45 30 64 28 37 47 44 67 70 45 50 57 43 39 46 51 45 43 40 55 19 94 43 44 50 52 49 50 42 42 40 50 34 48 55 63 81 73 77 70 76 89 96 65 99 84 122 117 111 103 81 95 86 153 141 144 143 137 152 161 189 165 156 161 152 151 105 124 181 133 121 137 101 137 144 96 107 110 107 133 129 137 113 121 122 125 147 149 216 150 163 107 150 158 161 155 142 145 170 199 157 160 163 181 203 110 141 112 147 149 120 120 122 115 139 142 161 123 126 150 87 69 85 99 100 120 75 49 43 114 114 105 98 112 72 85 87 69 23 17 16 19 17 27 20 29 25 34 36 29 20 59 98 75 78 75 66 85 87 90 58 79 75 71 67 74 69 66 31 54 44 63 49 42 56 53 52 43 26 24 33 26 34 25 31 28 30 28 25 21 31 19 38 35 28 32 39 51 31 48 52 46 42 53 35 44 37 40 35 45 52 36 28 33 27 46 38 28 28 30 52 36 22 22 26 22 44 57 82 64 96 83 50 96 54 64 68 59 53 59 67 67 75 51 35 39 44 33 51 35 33 41 29 33 34 28 25 30 21 34 26 22 33 16 5 10 10 10 16 10 14 16 14 18 21 17 9 10 15 7 8 9 10 14 30 6 8 11 10 7 7 4 8 4 20 12 14 13 6 7 11 5 8 6 5 8 6 6 11 18 18 16 23 25 26 38 24 28 9 30 35 29 20 27 23 21 23 23 24 24 26 25 16 14 25 19 22 23 15 11 24 23 20 15 14 13 11 18 26 17 12 17 31 15 17 12 18 12 5 10 5 10 11 5 5 10 8 10 7 14 14 9 9 3 12 9 5 7 10 4 3 9 7 6 9 18 8 12 27 8 10 19 9 22 21 31 15 12 17 22 24 28 29 27 28 19 18 15 23 24 33 36 34 45 44 32 54 50 46 67 37 41 33 21 22 31 16 16 25 15 22 20 16 13 23 18 17 24 16 18 26 26 27 27 14 20 28 23 38 14 20 8 19 20 15 11 11 13 24 16 26 23 23 23 24 23 36 28 23 12 25 19 20 23 31 19 39 33 28 28 34 65 54 87 41 58 51 50 43 61 32 32 33 26 30 18 16 45 21 21 24 28 28 17 19 19 12 20 16 17 19 8 13 12 19 13 20 16 17 23 31 14 29 40 23 14 14 20 11 12 18 
];
B = [
0 0 0
 297261 184535 112726
 351107 276234 74873
 294887 221792 73095
 479586 428575 51011
 274447 173595 100852
 904611 839908 64703
 377458 280048 97410
 138925 123437 15488
 348633 251492 97141
 60004 51050 8954
 71448 29805 41643
 25632 19725 5907
 100511 57460 43051
 278732 247845 30887
 281085 229324 51761
 144915 132276 12639
 827780 770412 57368
 203654 177142 26512
 359856 315652 44204
 156239 145335 10904
 428776 340718 88058
 333391 326535 6856
 189036 105831 83205
 406240 369027 37213
 143707 103555 40152
 581593 574030 7563
 364068 336755 27313
 176839 132060 44779
 396359 348021 48338
 109435 104878 4557
 348431 344961 3470
 367314 363911 3403
 108928 106902 2026
 461204 457736 3468
 152960 151105 1855
 334341 331496 2845
 146996 144761 2235
 360408 357759 2649
 330849 328379 2470
 165072 163366 1706
 318697 316491 2206
 117197 115694 1503
 364921 362682 2239
 306196 304211 1985
 106687 105528 1159
 327183 325210 1973
 156954 155748 1206
 308868 307127 1741
 120747 119675 1072
 315530 313899 1631
 334983 333111 1872
 95363 94639 724
 331257 329454 1803
 128454 127811 643
 327058 325110 1948
 292936 291317 1619
 157741 157015 726
 284280 282616 1664
 127378 126863 515
 25134144 25065668 68476
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
18 31 0 0
12 6 0 0
8 14 0 0
19 9 0 0
18 8 0 0
22 23 0 0
336 34 4 2
1923 28 4 7
9924 19 63 15
48361 80 78 23
194713 63 109 41
648668 80 155 63
1847538 85 193 94
4536972 142 207 137
7998824 176 218 191
8629767 143 221 287
7249449 216 192 359
4380236 216 259 324
1642818 268 347 326
329600 329 364 398
31335 412 415 441
1757 497 509 518
938 689 801 635
1132 642 627 954
1005 783 725 759
1411 1008 722 691
1209 1290 827 849
1661 6402 846 887
4870 6836 882 1260
1430 1414 1038 1813
28250 17639 1808 1167
3119 5069 1527 1296
6806 12240 1623 1625
7406 1824 1375 1286
11383 10392 1900 1496
4818 3575 1837 1494
1997 1995572 1171 2704
1615 1507 1073 1204
1900 2502 1358 1101
1501 1476 1247 2734
2432 1513 1230 1087
2620 1575 1540 1341
3241 2936 6407 4003
1440 1651 2105 1407
4515 2909 1624 1868
2209 1908 1310 1407
1358 1319 1454 1326
1162 1238 1209 1229
1183 1123 1282 1308
1153 1170 1537 1348
1129 1193 1534 2515
959 1018 1304 1612
1053 1065 1227 1111
832 836 1310 1248
799 762 808 776
692 789 749 854
584 550 871 1189
807 682 1047 1389
465 491 673 661
1409 963 704 788
591 498 454 482
507 449 446 441
396 511 501 600
376 478 495 536
378 386 560 557
414 445 409 387
351 358 412 411
40005 25985 11006 14380
432 425 588 444
460 455 551 528
2136 923 872 847
563 608 1189 923
611 647 599 562
591 577 643 834
616 629 615 638
725 731 589 570
442 463 425 453
376 346 317 354
301 270 295 294
247 227 213 210
166 164 148 149
107 111 163 178
4 4 4 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

];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 
];
