0 1 1 1 2 2 3 4 4 8 5 10 6 26 7 32 8 63 9 84 10 157 11 207 12 383 13 477 14 768 15 1108 16 1710 17 2261 18 3536 19 4605 20 6869 21 9339 22 13343 23 17653 24 25785 25 33463 26 46752 27 61549 28 85614 29 110861 30 153719 31 197345 32 268623 33 346845 34 463513 35 593363 36 797082 37 1011403 38 1335625 39 1703143 40 2232161 41 2820539 42 3683086 43 4630443 44 5985654 45 7548911 46 9675993 47 12121359 48 15528787 49 19360004 50 24600869 51 30673451 52 38749674 53 48071082 54 60547984 55 74920244 56 93880512 57 115958523 58 144580326 59 177961522 60 221484443 61 271672330 62 336441856 63 412236869 64 508583225 65 620986797 66 764526354 67 931053126 68 1142006140 69 1388563438 70 1697651671 71 2058583592 72 2511764272 73 3038082835 74 3694805328 75 4462806472 76 5412340800 77 6520350003 78 7893114561 79 9489103822 80 11456117644 81 13751221365 82 16559996084 83 19836315610 84 23846314981 85 28507165078 86 34187699036 87 40811642705 88 48840180213 89 58187830464 90 69513702762 91 82678485732 92 98569569250 93 117066224564 94 139296759633 95 165157106239 96 196212210075 97 232256140122 98 275418358416 99 325581383471 100 385428975593 101 454905145441 102 537715235229 103 633707347072 104 747828265442 105 880217958192 106 1037101089495 107 1218937572973 108 1434243346373 109 1683386163131 110 1977748416550 111 2318512498469 112 2720066141621 113 3184487967921 114 3731216199697 115 4362775368196 116 5104823917428 117 5961985655193 118 6966824370533 119 8126620954036 120 9485164326721 121 11051088267133 122 12882086316288 123 14992631999400 124 17455626607032 125 20292208154319 126 23599376917284 127 27404018721310 128 31833328532496 129 36927483389828 130 42847815672967 131 49651541605572 132 57551660675831 133 66620996420259 134 77137264668855 135 89206354364077 136 103180605507042 137 119205008261759 138 137741957165834 139 158979410541926 140 183517289255907 141 211617257240482 142 244039945764397 143 281143169906245 144 323917833038585 145 372823990053218 146 429141798492428 147 493504133989317 148 567531804819230 149 652071758160541 150 749226075830694 151 860087877892843 152 987360676564273 153 1132521851199368 154 1298985267321602 155 1488716041705305 156 1706119782413302 157 1953718945546133 158 2237159911759953 159 2559810653128870 160 2928798281018815 161 3348548989458112 162 3828213880284036 163 4373482005892953 164 4996031474204893 165 5703363213730507 166 6510191407899300 167 7426323491354963 168 8470571331016177 169 9655466053763721 170 11004940862448131 171 12535421264102684 172 14276982218541346 173 16250913261477313 174 18495533582549021 175 21038009834832730 176 23926910411781868 177 27197487224267408 178 30910726634704557 179 35112100506948054 180 39878977738904608 181 45269130430982836 182 51380350634185009 183 58287194044380755 184 66112172829138227 185 74950843425573757 186 84958109203359552 187 96255117134536390 188 109037032789798990 189 123459075048254687 190 139765494248975634 191 158154243652725843 192 178933028964669912 193 202351995600032207 194 228797735143034935 195 258589256327606900 196 292209169519908774 197 330062379652376168 198 372755233209954819 199 420797879118372222 200 474949924178440917 201 535858382499168860 202 604469998209488776 203 681602951498593276 204 768442722507521467 205 866016802699934594 206 975806573128897210 207 1099109894976463253 208 1237769142193431399 209 1393418370833347382 210 1568359165453649687 211 1764637400389601829 212 1985121061741814752 213 2232384071195467334 214 2509986390283623258 215 2821157802138645511 216 3170331691133370442 217 3561540563424350176 218 4000296542264293855 219 4491653633823533342 220 5042439711969890441 221 5658973508967646967 222 6349737459577050137 223 7122600603458757512 224 7988081610557767736 225 8956007982620839024 226 10039383853757697376 227 11250458824752188828 228 12605345815983124340 229 14119256722686962487 230 15812128487684804543 231 17702900871213130037 232 19816167338452610153 233 22175461948498103854 234 24811188822710835956 235 27752501332823279102 236 31036927096029872678 237 34700647868127082329 238 38789874488050040194 239 43349440893231418755 240 48436334172160086586 241 54105950643940876971 242 60428480892736677161 243 67472485630875902043 244 75324216862246583436 245 84068395839436389390 246 93811153977474368659 247 104656929963528367567 248 116736155117859116280 249 130177721634946382260 250 145141613653255254558 251 161786697956099945412 252 180309388412271909528 253 200905076267702317640 254 223814638130838256013 255 249278603034058932553 256 277591858079581147726 257 309050115391795201108 258 344014666135604060743 259 382848393595584935815 260 425993474292533097172 261 473895496584578892254 262 527094789200068673193 263 586137905508126025420 264 651685455443117677864 265 724406666609782639862 266 805108474111178533825 267 894610716239589689743 268 993897627538001364885 269 1103972476000249822304 270 1226036249280132771820 271 1361314848472732013221 272 1511272421941739158554 273 1677407328347479568762 274 1861502245281298081338 275 2065386819686501019427 276 2291232149958057571218 277 2541269197508710888915 278 2818139898203175513353 279 3124565243348838789037 280 3463756227787998723408 281 3839028356002404739637 282 4254284938537980038844 283 4713560916690632213365 284 5221597406034221972730 285 5783305162526614946275 286 6404436680385152402700 287 7090963690409553264550 288 7849866260459146790210 289 8688397735778883311520 290 9615021496101675518249 291 10638547764528112486897 292 11769227906961473785882 293 13017754448625646022799 294 14396544505207539171761 295 15918561472844374491245 296 17598835081677498740862 297 19453080404278061820223 298 21499472483925326049055 299 23757048160191386449353 300 26247784689795036445848 301 28994719375722011617927 302 32024408869299588490822 303 35364729307115823197046 304 39047742642744028990787 305 43107155022144643172781 306 47581670758740149050979 307 52512008591192107304564 308 57944861097100767252986 309 63929409421555170051556 310 70521936831116173077466 311 77781806042887039856406 312 85776849846067298789127 313 94578658044082868289340 314 104268932679562063106388 315 114933992434020567804868 316 126672167924053694661883 317 139587467639854409286474 318 153798212490576730628329 319 169429627424386226150264 320 186624002762965738408234 321 205532069770729121786862 322 226324819200431435692209 323 249183573616023973228201 324 274313766175215648278064 325 301933354623700970995732 326 332289010051954100980065 327 365642657425610675119115 328 402290284066268058512528 329 442546461063727288644209 330 486766259466382547009358 331 535327216083124084192798 332 588655044734611173864594 333 647202716669901356942536 334 711480312345841952412214 335 782031003722793845617526 336 859465787577974203556413 337 944435559734410117706296 338 1037671812450297823364682 339 1139954294173444074476518 340 1252158216717781517989154 341 1375217169809802110677280 342 1510178012379096445180826 343 1658157833008658108140064 344 1820408159295297445890029 345 1998265207001919708320690 346 2193224310028606386784114 347 2406882956508589583009369 348 2641027233268059415896854 349 2897565836245894681158652 350 3178631080924577536598933 351 3486502756492014430367638 352 3823725087876194014587922 353 4193019697809910686002933 354 4597421342688418963833825 355 5040177267392305907092703 356 5524905583607472810157110 357 6055479342482278591231215 358 6636209837800940163537644 359 7271714268640047983863432 360 7967128245374191523961155 361 8727953063763645092767388 362 9560303400306440556335015 363 10470731712276174797631885 364 11466514638636678320199704 365 12555452888106046692292355 366 13746203016935467753508384 367 15048046941474526431814321 368 16471278141040714119434135 369 18026937132037133246254108 370 19727257796670146270974377 371 21585366390415961120317891 372 23615798106672680564722596 373 25834151089607522093424794 374 28257687136509326167044213 375 30904935361362451560821849 376 33796385821946472420866549 377 36954039380855958324817069 378 40402209997161642761344482 379 44167008143476155478185874 380 48277272824179053016465650 381 52763980984106197062913670 382 57661323051937676610997238 383 63006033411493140654903440 384 68838633288354720749287690 385 75202664162471935950728148 386 82146130200799998200988287 387 89720623492479557468820261 388 97982987562191086192573849 389 106994327522384411380393620 390 116821931319280642809349052 391 127538138612426582817483087 392 139222568191765875192596888 393 151960830061963736258797124 394 165847092853412196995034872 395 180982629404086709178039215 396 197478779633230204466449129 397 215455292333361044944140957 398 235043757458697877114840396 399 256385721847729792795457034 400 279636643063397772368263630 401 304963766233800609573103583 402 332550684348282466212301591 403 362594922973533630501226263 404 395313218034035192153139146 405 430938777997730200708235326 406 469727360936115524784376191 407 511954195878555728176299704 408 557920988034429148158137691 409 607952425376736129641029668 410 662404279525813453582836886 411 721659455329418549110870576 412 786137313360065399561838935 413 856289240094729624149703978 414 932609387735545217225563079 415 1015629660384499308897618174 416 1105932123940645493326976269 417 1204143351840402664420200972 418 1310948700621644906729053743 419 1427085986034359253190253350 420 1553361919935135949077731338 421 1690644973894911660211319765 422 1839884358428705605700339707 423 2002101998509478040522946167 424 2178414355079209074245269699 425 2370023479926355677990741725 426 2578242128566691287152192745 427 2804483696764432939454644250 428 3050291196910125872343573848 429 3317325980553822207705845276 430 3607401041556107982203675690 431 3922468488294006689994679139 432 4264657849796132228057886078 433 4636262035090582986655774779 434 5039781503071303000087538127 435 5477908587719128211514460636 436 5953578238082922264988638889 437 6469950684254200494904308070 438 7030469774425486298774392152 439 7638843623061161110239992986 440 8299111835544327951665748297 441 9015624002895720675078965952 442 9793116898930547904029194404 443 10636690814749718282250405176 444 11551898269547250492222309957 445 12544717728874888060001760244 446 13621655767546514313844164480 447 14789718017600395148572109343 448 16056526440027815370166709884 449 17430287557229998475768929987 450 18919927160392589333212091605 451 20535055239346418019720446282 452 22286121022240728997756851372 453 24184374478339726486399033015 454 26242044220466353231784079423 455 28472295741260937096210651202 456 30889435671426672519984013455 457 33508866042931731713419811979 458 36347319251524796528290452038 459 39422808279190419016735322764 460 42754896204835449890839740549 461 46364642785127303780312542016 462 50274913772261485602860192205 463 54510323017231084893223928160 464 59097588079138975370291666681 465 64065467996884244228894118222 466 69445171027608251985073099366 467 75270288877956814800373632675 468 81577264473080145333573937107 469 88405321750616247375946410489 470 95797003175020050505027462074 471 103798095608727285892095400434 472 112458246417491821732909713860 473 121830886954793556534829977626 474 131973939096041726195278025571 475 142949735528121206512217156118 476 154825831190290410957256709586 477 167674921649942376351478380165 478 181575772879597650570772828691 479 196613140444241586488155895494 480 212878835339446730604815337898 481 230471643610648186193592069584 482 249498549879056932747501613401 483 270074659998517857840969836038 484 292324602514231876989507981635 485 316382459227509337292308111144 486 342393371146457892777410228391 487 370513477505552004122842757557 488 400911758423046692469011968567 489 433769987376936639297767158376 490 469284841191626898039184443452 491 507667874257693715008581961819 492 549147935512003780386288509066 493 593971167043197708250137455767 494 642403776052085544736242084804 495 694732066851773708735590499822 496 751265613938731675998573367868 497 812337341367844597302427885340 498 878307156319552362643341415634 499 949562082277155243480129796619 500 1026520424337368957918081040352 #