A = [
66163 13867 12411 143601 9390 10856 11228 11120 11771 11879 13214 12979 13337 13936 14412 14180 14034 14165 14245 14081 14209 14016 14123 13964 75574 74966 75728 75788 77601 146196 144628 144317 144774 144325 150865 149663 148910 149397 148429 148003 147088 146980 146923 145822 146459 145420 145011 144171 143596 142993 141959 141226 141957 141646 141368 139644 140205 139488 138834 138251 137424 137689 136305 135409 135848 134891 134053 133476 133388 131054 131355 130168 128555 128343 128350 126795 126814 125921 124130 122912 122625 120595 121079 120276 118547 118175 116803 116162 114256 113661 112299 111301 110539 109345 108365 107910 106418 104859 104622 104292 102232 100851 99099 98972 97734 97058 96166 94190 93837 92888 91589 90132 89233 88198 86464 85612 85427 84175 82885 82247 81158 80333 79035 78543 76944 76038 75191 74180 73442 72182 71338 70526 69919 67963 67482 66813 66114 65738 64683 64050 62770 61197 61059 59813 59296 57944 57502 56901 55714 55327 55323 54209 53361 52637 51968 51176 50265 49503 49307 48100 47618 46683 45884 45771 45104 44376 43670 43023 42628 42040 41004 40997 40122 39285 38746 38297 37577 36939 36546 36180 35099 35170 34234 33764 33371 32810 32747 32205 31347 30730 30799 30090 29880 29205 28775 28363 28045 27668 27481 26532 26335 26057 25818 25485 24743 24623 24030 23748 23235 22986 22989 22456 22289 22031 21562 21137 20834 20623 20040 19905 19589 19396 19222 18661 18693 18401 17981 17490 17290 17179 16654 16631 16308 15985 16114 15503 15315 15015 14763 14660 14271 14366 14059 13740 13384 13365 13046 12803 12829 12469 12435 12374 12111 12031 11862 11627 11377 11315 11220 10913 10744 10560 10402 10307 10077 10027 9817 9832 9666 9507 9147 8972 9179 8782 8673 8591 8333 8195 8247 8127 8009 7942 7872 7547 7666 7332 7278 7417 7062 6957 6840 6683 6547 6531 6443 6563 6283 6218 6195 6125 5889 5866 5739 5632 5670 5468 5426 5350 5293 5198 5150 5063 5029 4863 4818 4869 4777 4653 4565 4453 4431 4430 4476 4244 4132 4076 4148 4002 3993 3842 3931 3889 3683 3694 3715 3540 3446 3492 3489 3406 3331 3235 3278 3167 3239 3097 3172 3134 3036 2956 2958 2861 2727 2742 2657 2644 2657 2766 2586 2619 2771 2472 2526 2495 2472 2431 2340 2378 2305 2274 2310 2231 2160 2148 2179 2132 2082 2073 2012 2018 2037 1869 1858 1938 1812 1884 1826 1828 1763 1807 1748 1711 1745 1675 1672 1654 1634 1562 1576 1595 1519 1544 1529 1422 1515 1504 1419 1449 1409 1459 1313 1369 1404 1375 1365 1362 1294 1216 1257 1218 1297 1300 1181 1213 1176 1093 1102 1165 1174 1099 1134 1056 1074 1052 1083 1060 1070 989 1077 1063 1017 960 974 994 965 991 959 980 900 1001 943 917 885 911 951 893 893 903 879 797 819 890 820 893 907 890 842 820 785 782 762 776 785 794 768 781 781 760 773 745 680 777 746 756 735 712 750 690 671 699 701 663 663 687 679 703 674 607 643 662 621 620 617 616 621 646 609 658 617 651 593 644 581 645 607 616 585 557 609 597 605 607 646 534 597 529 568 518 553 541 559 541 502 542 523 573 515 536 518 507 482 527 526 489 482 514 471 480 457 482 488 500 508 491 474 445 504 484 517 460 470 483 529 478 443 478 466 455 471 475 501 484 483 432 462 450 422 438 447 465 459 410 420 465 450 421 412 433 435 465 462 460 440 460 475 448 441 438 426 423 446 443 436 472 447 541 555 535 448 419 391 454 444 444 413 390 436 410 413 430 433 404 444 368 399 413 418 387 449 377 398 386 443 421 427 426 385 371 387 393 400 413 400 394 405 410 387 414 359 418 433 383 403 364 405 370 414 371 413 381 403 363 425 397 424 414 392 406 387 390 387 416 405 335 360 382 366 383 371 361 394 343 432 403 363 377 360 366 348 365 366 351 367 361 391 369 377 400 376 384 367 379 411 376 368 364 398 395 409 411 411 419 424 388 412 400 393 384 404 413 380 362 430 397 419 367 406 374 384 357 407 385 407 349 362 410 396 361 347 356 381 381 407 403 372 341 408 384 373 363 436 362 360 354 361 397 341 395 340 367 387 368 360 343 356 355 350 333 354 359 363 353 316 354 340 338 400 354 359 365 387 375 340 335 402 362 368 368 354 376 351 359 340 365 386 354 334 345 362 340 341 312 343 343 295 320 334 370 371 394 366 379 329 384 334 345 383 403 380 390 362 391 365 334 338 320 354 311 328 357 307 367 379 315 331 331 327 321 314 345 305 334 321 281 316 330 317 335 332 310 301 370 351 307 339 301 309 350 335 288 328 334 357 360 351 357 343 353 349 326 314 329 338 331 324 341 330 309 314 330 359 334 342 328 320 349 324 326 342 358 328 334 344 356 353 337 337 352 344 322 312 357 306 353 314 315 312 325 355 295 368 365 350 332 331 302 327 306 371 373 341 345 343 348 327 337 335 351 326 324 311 314 350 317 354 348 341 307 338 316 336 313 322 349 292 367 315 331 338 333 304 348 334 290 327 354 299 340 335 344 360 335 293 345 311 331 286 312 324 337 313 369 348 344 327 322 329 292 282 311 304 304 323 330 287 322 370 323 318 345 360 327 312 292 354 318 368 313 340 367 311 344 316 313 322 328 256 301 296 313 313 299 314 300 307 322 332 286 283 354 323 333 302 271 324 349 309 262 312 325 297 283 316 321 314 287 277 289 288 282 297 288 291 324 276 274 251 304 294 293 302 297 264 294 281 273 290 252 272 278 282 303 297 287 260 306 279 275 266 295 272 282 307 313 301 306 285 280 321 279 267 287 293 309 287 351 312 316 281 251 293 289 319 298 275 277 297 294 272 309 303 310 308 305 255 322 310 279 297 263 319 303 318 282 312 320 334 319 268 274 316 328 296 321 322 279 333 295 302 311 310 348 318 320 307 319 327 295 326 300 324 284 311 302 330 332 304 296 330 337 328 310 309 307 336 315 309 309 318 300 327 352 311 287 294 325 329 322 292 308 296 263 265 306 309 307 298 299 314 316 293 291 332 324 290 293 324 306 303 296 304 301 319 293 314 295 299 324 307 291 279 285 263 279 296 298 281 257 269 285 265 269 296 313 301 280 269 282 271 285 243 261 267 227 267 237 242 273 293 257 251 224 242 285 225 272 228 241 273 228 269 239 251 231 243 280 232 255 254 255 240 269 238 253 273 265 282 304 238 246 275 261 262 289 247 263 233 249 264 255 287 285 256 267 274 268 266 262 302 290 271 269 293 290 269 278 283 294 296 280 321 258 291 310 256 274 317 289 271 275 299 293 259 279 259 297 279 276 303 277 290 290 262 271 268 261 266 306 265 304 320 285 308 331 278 265 273 249 262 268 282 250 267 305 288 251 253 262 278 266 293 278 244 248 243 264 284 247 249 255 275 251 274 247 247 270 266 280 256 258 283 273 262 259 274 247 282 260 285 255 285 253 271 251 256 252 249 272 279 233 249 254 238 228 256 266 243 241 249 223 250 245 257 210 225 251 272 281 245 196 240 278 228 230 255 237 243 225 272 229 247 217 230 218 219 237 249 223 245 227 245 240 231 224 241 214 255 231 228 222 213 253 215 232 219 204 242 229 245 219 227 239 232 239 240 248 225 209 249 234 233 231 229 215 239 227 238 217 247 225 216 257 257 235 264 225 244 257 223 232 243 249 226 265 262 259 207 200 247 224 233 216 208 225 221 252 215 218 211 206 205 202 213 246 224 222 209 202 223 204 196 186 184 225 245 232 242 222 210 216 211 203 232 207 219 243 226 219 243 235 222 243 202 208 225 190 218 182 237 230 232 227 252 212 214 207 221 216 224 224 211 210 222 233 220 247 230 232 267 221 242 223 237 233 222 195 207 233 215 230 220 231 222 219 217 202 202 198 203 186 207 225 216 196 199 207 175 206 188 217 190 189 173 194 192 194 209 197 193 194 192 207 203 218 196 209 194 215 201 215 211 222 209 216 206 202 228 207 193 166 221 226 234 219 233 212 231 284 238 230 204 238 229 183 206 219 220 236 206 240 238 230 223 247 248 263 223 214 241 228 223 265 214 215 225 257 259 237 224 234 258 246 247 195 247 227 265 230 236 231 246 240 217 196 219 217 214 236 214 240 216 221 236 212 199 238 224 217 207 208 191 193 215 229 175 192 208 223 195 205 197 199 207 230 212 201 204 181 198 227 191 204 189 188 175 203 216 218 174 175 223 197 193 201 191 238 179 209 172 220 200 199 198 205 204 187 169 225 210 169 209 225 208 164 198 203 201 190 224 227 197 203 230 189 214 216 213 226 217 171 200 199 218 191 182 184 222 216 191 204 233 247 210 227 224 214 186 203 226 191 218 195 225 204 216 207 226 229 218 198 207 215 232 230 204 230 218 195 207 201 211 189 192 202 221 217 199 186 214 198 196 187 218 181 202 193 198 229 207 200 206 204 188 185 176 209 221 208 225 219 185 211 214 198 219 247 205 220 215 232 204 199 219 198 233 198 177 209 212 188 217 204 214 205 200 165 213 165 198 186 185 219 213 213 222 218 212 223 195 174 166 207 232 217 211 193 184 201 205 229 186 175 184 212 188 198 199 214 201 178 208 188 189 209 208 211 194 217 177 189 176 215 180 165 162 173 171 194 222 215 176 189 175 177 171 180 191 200 180 202 211 201 175 190 194 197 164 200 199 199 198 169 204 169 233 190 165 182 174 185 164 170 166 169 181 179 180 187 169 174 171 180 178 183 163 189 164 207 190 185 185 180 202 197 177 201 205 171 194 184 212 193 181 186 148 173 173 161 178 193 202 187 184 232 199 176 183 196 185 187 170 172 204 196 185 160 181 184 163 158 193 198 172 191 178 180 184 177 171 181 
];
B = [
0 0 0
 6237 2785 3452
 4247 1560 2687
 9848 5177 4671
 3651 1647 2004
 3870 1669 2201
 5322 2295 3027
 6563 2918 3645
 4697 1941 2756
 11613 5207 6406
 4774 2075 2699
 5278 2285 2993
 7387 2989 4398
 10218 4779 5439
 10638 3437 7201
 14250 6804 7446
 7761 3538 4223
 10806 4228 6578
 8109 3682 4427
 12551 6044 6507
 10357 4692 5665
 14108 7608 6500
 12914 6271 6643
 9630 4814 4816
 15404 8186 7218
 21932 11007 10925
 3209 1621 1588
 52527 31557 20970
 1998 1112 886
 3655 2367 1288
 2759 1545 1214
 4225 2504 1721
 2065 1075 990
 12922 8076 4846
 2597 1139 1458
 3825 2769 1056
 2221 1339 882
 3826 2168 1658
 295 204 91
 16340 10288 6052
 9 9 0
 172 135 37
 695 540 155
 5058 3990 1068
 415 331 84
 398 298 100
 622 483 139
 1697 1311 386
 37584 24162 13422
 65 51 14
 638 518 120
 496 391 105
 851 672 179
 2801 2231 570
 45782 32003 13779
 1208 998 210
 1238 998 240
 3053 2592 461
 75696 63130 12566
 28988 23966 5022
 8798131 7361789 1436342
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 0 0 0
 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 = [
0 11 0 0
0 0 0 0
1 2 0 0
0 2 0 0
1 0 0 0
0 6 56 0
36 1 123 6
82 4 161 13
202 7 198 26
1377 1 282 53
8331 3 331 93
30088 10 382 162
66906 9 456 235
114101 58 559 360
145576 112 592 450
153646 265 869 761
127651 469 1119 1075
84738 880 1623 1564
46189 1455 2174 2191
20797 2335 3027 2879
9234 3822 3585 3615
5808 5677 4723 4630
5490 8292 5911 5868
6207 10903 7573 7466
7643 13488 8879 8917
8896 15579 10609 10474
9674 19277 11866 11546
10989 21639 13200 13021
12425 26217 15411 15053
14360 28960 17589 17295
16207 30582 19070 18665
18755 32680 21632 21672
20580 34815 24024 23889
22741 36476 26296 25685
25437 37810 29193 28957
27902 39224 31326 31516
30005 39860 33642 32943
32406 41862 35713 35232
34886 43361 38624 37612
37305 44714 40446 40092
39502 46101 42338 41988
41186 46536 43291 42896
41830 47432 44513 43423
43442 47411 46052 45001
43673 48072 46138 45584
44546 47978 46230 46045
44541 47819 45986 46457
43992 47179 46029 45262
43966 46766 45046 45352
43481 45450 45226 44218
43681 44646 43945 43853
43015 44179 43846 43427
42889 43827 43360 43052
42430 43059 42855 41914
42328 43235 43263 42420
42773 42567 42453 42137
42952 42999 43307 42613
42925 43538 43300 43136
44928 44907 45084 44640
46708 46578 46922 46375
48059 48386 48466 47862
49871 49531 50382 49336
51321 51305 51337 50948
51434 52169 51783 51467
48839 49226 48564 48391
44409 44132 44649 44052
38111 37632 38005 37755
31136 30833 30933 30480
23604 23453 23562 23167
15632 15795 15880 16034
7034 6952 6949 6857
857 879 813 859
0 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 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
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 
];
