1 1 2 1 3 1 4 2 5 3 6 2 7 3 8 4 9 4 10 3 11 5 12 11 13 11 14 11 15 5 16 8 17 15 18 24 19 24 20 15 21 8 22 13 23 42 24 59 25 89 26 59 27 42 28 13 29 21 30 57 31 139 32 191 33 191 34 139 35 57 36 21 37 34 38 161 39 332 40 748 41 685 42 748 43 332 44 161 45 34 46 55 47 218 48 796 49 1573 50 2379 51 2379 52 1573 53 796 54 218 55 55 56 89 57 617 58 1903 59 6259 60 8357 61 13785 62 8357 63 6259 64 1903 65 617 66 89 67 144 68 835 69 4563 70 13176 71 29493 72 43004 73 43004 74 29493 75 13176 76 4563 77 835 78 144 79 233 80 2364 81 10934 82 52497 83 103842 84 253150 85 223270 86 253150 87 103842 88 52497 89 10934 90 2364 91 233 92 377 93 3199 94 26209 95 110739 96 366761 97 793041 98 1168723 99 1168723 100 793041 101 366761 102 110739 103 26209 104 3199 105 377 106 610 107 9057 108 62835 109 441340 110 1295168 111 4669709 112 6098749 113 10204445 114 6098749 115 4669709 116 1295168 117 441340 118 62835 119 9057 120 610 121 987 122 12256 123 150636 124 931361 125 4575191 126 14671984 127 31928221 128 47403200 129 47403200 130 31928221 131 14671984 132 4575191 133 931361 134 150636 135 12256 136 987 137 1597 138 34699 139 361156 140 3713195 141 16168709 142 86434175 143 167211867 144 414060681 145 367167586 146 414060681 147 167211867 148 86434175 149 16168709 150 3713195 151 361156 152 34699 153 1597 154 2584 155 46955 156 865882 157 7836336 158 57141283 159 271693559 160 875862454 161 1930022303 162 2853703400 163 2853703400 164 1930022303 165 875862454 166 271693559 167 57141283 168 7836336 169 865882 170 46955 171 2584 172 4181 173 132938 174 2076002 175 31247585 176 201968011 177 1601479258 178 4590346691 179 16873527728 180 22195697956 181 37025661591 182 22195697956 183 16873527728 184 4590346691 185 1601479258 186 201968011 187 31247585 188 2076002 189 132938 190 4181 191 6765 192 179893 193 4977375 194 65947255 195 713913289 196 5034665244 197 24059996616 198 78695767649 199 172661632049 200 256191351834 201 256191351834 202 172661632049 203 78695767649 204 24059996616 205 5034665244 206 713913289 207 65947255 208 4977375 209 179893 210 6765 211 10946 212 509309 213 11933643 214 262980516 215 2523592759 216 29682509736 217 126124391879 218 688530349845 219 1344020681392 220 3328097943189 221 2960154980175 222 3328097943189 223 1344020681392 224 688530349845 225 126124391879 226 29682509736 227 2523592759 228 262980516 229 11933643 230 509309 231 10946 232 17711 233 689202 234 28611925 235 555025545 236 8920910386 237 93325900298 238 661229366397 239 3211944777926 240 10463714737629 241 23043936155737 242 34209042050748 243 34209042050748 244 23043936155737 245 10463714737629 246 3211944777926 247 661229366397 248 93325900298 249 8920910386 250 555025545 251 28611925 252 689202 253 17711 254 28657 255 1951253 256 68599559 257 2213339483 258 31535904373 259 550249461287 260 3466736635802 261 28109523667827 262 81475267520350 263 299631026725211 264 395633105556077 265 660415936461789 266 395633105556077 267 299631026725211 268 81475267520350 269 28109523667827 270 3466736635802 271 550249461287 272 31535904373 273 2213339483 274 68599559 275 1951253 276 28657 277 46368 278 2640455 279 164473454 280 4671332880 281 111482428201 282 1730155635975 283 18176404398121 284 131151482722019 285 634495286031292 286 2075337181737205 287 4576602971459261 288 6793892871530797 289 6793892871530797 290 4576602971459261 291 2075337181737205 292 634495286031292 293 131151482722019 294 18176404398121 295 1730155635975 296 111482428201 297 4671332880 298 164473454 299 2640455 300 46368 301 75025 302 7475596 303 394339672 304 18628563209 305 394104351253 306 10201324308311 307 95303022729314 308 1147888798618522 309 4941445395589369 310 26993206361408199 311 52949704219418919 312 131298926225305264 313 116764729695106769 314 131298926225305264 315 52949704219418919 316 26993206361408199 317 4941445395589369 318 1147888798618522 319 95303022729314 320 10201324308311 321 394104351253 322 18628563209 323 394339672 324 7475596 325 75025 326 121393 327 10116051 328 945464381 329 39316357723 330 1393214372302 331 32076766175871 332 499702347782465 333 5356133004109719 334 38485871527375022 335 187004284759246349 336 612716308409716945 337 1351272677623405446 338 2007387494182064401 339 2007387494182064401 340 1351272677623405446 341 612716308409716945 342 187004284759246349 343 38485871527375022 344 5356133004109719 345 499702347782465 346 32076766175871 347 1393214372302 348 39316357723 349 945464381 350 10116051 351 121393 352 196418 353 28640333 354 2266835107 355 156788159916 356 4925225989915 357 189133666816468 358 2620121827047447 359 46881307964290531 360 299753511085726117 361 2432597881670033668 362 7090652384913649818 363 26124203051441861234 364 34516845882348995654 365 57661136320504955250 366 34516845882348995654 367 26124203051441861234 368 7090652384913649818 369 2432597881670033668 370 299753511085726117 371 46881307964290531 372 2620121827047447 373 189133666816468 374 4925225989915 375 156788159916 376 2266835107 377 28640333 378 196418 379 317811 380 38756384 381 5434939417 382 330908274229 383 17411465057517 384 594711922601130 385 13738355076135267 386 218757630164632164 387 2334722412900596908 388 16854154605700168507 389 82061379432657703434 390 268930837885488088970 391 593634601556995477709 392 882008408477368246655 393 882008408477368246655 394 593634601556995477709 395 268930837885488088970 396 82061379432657703434 397 16854154605700168507 398 2334722412900596908 399 218757630164632164 400 13738355076135267 401 594711922601130 402 17411465057517 403 330908274229 404 5434939417 405 38756384 406 317811 407 514229 408 109726191 409 13030752556 410 1319617809715 411 61552408000148 412 3506612483349207 413 72036070268779700 414 1914792777220306831 415 18184985322655919909 416 219257064569401667499 417 949753598546226522068 418 5200019052667730729325 419 10210468958759191337054 420 25345770184970911669729 421 22542682942448533813110 422 25345770184970911669729 423 10210468958759191337054 424 5200019052667730729325 425 949753598546226522068 426 219257064569401667499 427 18184985322655919909 428 1914792777220306831 429 72036070268779700 430 3506612483349207 431 61552408000148 432 1319617809715 433 13030752556 434 109726191 435 514229 436 832040 437 148482575 438 31242393432 439 2785112342748 440 217598149193659 441 11026238958822335 442 377717264790026986 443 8934927520599544525 444 141642965069643493152 445 1519168763899405470347 446 10992423449758288598364 447 53536524385102492281693 448 175631474817724741362098 449 387820681330330173608598 450 576287548733845212698866 451 576287548733845212698866 452 387820681330330173608598 453 175631474817724741362098 454 53536524385102492281693 455 10992423449758288598364 456 1519168763899405470347 457 141642965069643493152 458 8934927520599544525 459 377717264790026986 460 11026238958822335 461 217598149193659 462 2785112342748 463 31242393432 464 148482575 465 832040 466 1346269 467 420380482 468 74906430076 469 11106659897377 470 769246627275189 471 65014428623542105 472 1980544397921352391 473 78208486806923613034 474 1103264661881903004794 475 19763571322318255653060 476 127228429501612114263211 477 1035257083968620609295229 478 3021219695700078877111954 479 11146531461535263383405823 480 14733931583071097087185367 481 24616708332260554368059831 482 14733931583071097087185367 483 11146531461535263383405823 484 3021219695700078877111954 485 1035257083968620609295229 486 127228429501612114263211 487 19763571322318255653060 488 1103264661881903004794 489 78208486806923613034 490 1980544397921352391 491 65014428623542105 492 769246627275189 493 11106659897377 494 74906430076 495 420380482 496 1346269 497 2178309 498 568863057 499 179594860890 500 23441105903195 501 2719419298630255 502 204432609495303514 503 10384915669802384595 504 364943721554036128431 505 8593427804925432628543 506 136938491492677914040377 507 1472585180143692396565191 508 10658917936184009599427409 509 51972659435172996158114853 510 170577277155300267493605678 511 376732123634099868264086102 512 559911922932219071506247881 513 559911922932219071506247881 514 376732123634099868264086102 515 170577277155300267493605678 516 51972659435172996158114853 517 10658917936184009599427409 518 1472585180143692396565191 519 136938491492677914040377 520 8593427804925432628543 521 364943721554036128431 522 10384915669802384595 523 204432609495303514 524 2719419298630255 525 23441105903195 526 179594860890 527 568863057 528 2178309 529 3524578 530 1610552121 531 430594731585 532 93480050142148 533 9613618046412833 534 1205405243851711516 535 54452999736717363990 536 3194410143829165633787 537 66935179668454639950677 538 1781518723873420709901909 539 17044335134189161401888305 540 206123008769217527530617912 541 894081882471128984068048221 542 4903087924743245396022249055 543 9633269456097686298937715371 544 23922046664013142920406970568 545 21280113498540739803695888298 546 23922046664013142920406970568 547 9633269456097686298937715371 548 4903087924743245396022249055 549 894081882471128984068048221 550 206123008769217527530617912 551 17044335134189161401888305 552 1781518723873420709901909 553 66935179668454639950677 554 3194410143829165633787 555 54452999736717363990 556 1205405243851711516 557 9613618046412833 558 93480050142148 559 430594731585 560 1610552121 561 3524578 562 5702887 563 2179415178 564 1032389358312 565 197293868625593 566 33985809888354595 567 3790302222713624708 568 285522887940734484844 569 14906095216500154433380 570 521366693080388229524488 571 12343949121579492430771334 572 197279624086107393583286258 573 2122271751130440546784473706 574 15381062930177282842747375127 575 75036863999136489536206443473 576 246337044928823893079447791927 577 544192162956737873417531541257 578 808848617600401888644827292643 579 808848617600401888644827292643 580 544192162956737873417531541257 581 246337044928823893079447791927 582 75036863999136489536206443473 583 15381062930177282842747375127 584 2122271751130440546784473706 585 197279624086107393583286258 586 12343949121579492430771334 587 521366693080388229524488 588 14906095216500154433380 589 285522887940734484844 590 3790302222713624708 591 33985809888354595 592 197293868625593 593 1032389358312 594 2179415178 595 5702887 596 9227465 597 6170310577 598 2475245770817 599 786782083921875 600 120145755441580665 601 22348943212275192096 602 1497132511872713921599 603 130475680407827238846999 604 4060997635437798949369842 605 160591103564328551871120607 606 2283421280139060944052315854 607 41041287447895923495311417897 608 264605896989877753962718745391 609 2156955383952093908382755438443 610 6299368388210775930001809132924 611 23252876265116093266166517226673 612 30746194994798929451472183768985 613 51372731796521720910677635900432 614 30746194994798929451472183768985 615 23252876265116093266166517226673 616 6299368388210775930001809132924 617 2156955383952093908382755438443 618 264605896989877753962718745391 619 41041287447895923495311417897 620 2283421280139060944052315854 621 160591103564328551871120607 622 4060997635437798949369842 623 130475680407827238846999 624 1497132511872713921599 625 22348943212275192096 626 120145755441580665 627 786782083921875 628 2475245770817 629 6170310577 630 9227465 631 14930352 632 8349725755 633 5934622998382 634 1660539172083124 635 424736195625649529 636 70274523246453446747 637 7850181300039074208181 638 608840202175039378730337 639 31631703353566956819427289 640 1112722330339749903765499281 641 26429621286196640618757790643 642 422571284038331366838884306765 643 4552141110082636572524875326127 644 33010924537761829201058177881436 645 161091318809659732647268813272943 646 529002915832828700359012373619338 647 1168780006278751916887156017437869 648 1737297054994791202987003845164301 649 1737297054994791202987003845164301 650 1168780006278751916887156017437869 651 529002915832828700359012373619338 652 161091318809659732647268813272943 653 33010924537761829201058177881436 654 4552141110082636572524875326127 655 422571284038331366838884306765 656 26429621286196640618757790643 657 1112722330339749903765499281 658 31631703353566956819427289 659 608840202175039378730337 660 7850181300039074208181 661 70274523246453446747 662 424736195625649529 663 1660539172083124 664 5934622998382 665 8349725755 666 14930352 667 24157817 668 23639553244 669 14228789140865 670 6622012730950417 671 1501516584832991291 672 414363190246398835006 673 41162260631863385243841 674 5329290632576800586093834 675 246384104674659348197888561 676 14476225222795054408117664843 677 305912064134386076073747216438 678 8171900003555132635325169537317 679 78313010736533041004499591572976 680 948925328874738037758757536936074 681 4119572202327369452780798242518131 682 22604929399722652356413213101860425 683 44431092690297610512707652026631752 684 110354829141528982761094287423120236