0 1 1 1 2 2 3 4 4 6 5 9 6 14 7 18 8 24 9 34 10 42 11 52 12 68 13 82 14 101 15 126 16 147 17 175 18 213 19 246 20 289 21 344 22 392 23 453 24 530 25 598 26 687 27 791 28 885 29 1007 30 1151 31 1276 32 1438 33 1629 34 1806 35 2018 36 2262 37 2490 38 2775 39 3091 40 3387 41 3754 42 4165 43 4542 44 5011 45 5527 46 6012 47 6600 48 7245 49 7864 50 8614 51 9405 52 10167 53 11100 54 12103 55 13043 56 14185 57 15411 58 16589 59 17983 60 19474 61 20913 62 22630 63 24428 64 26181 65 28258 66 30449 67 32552 68 35055 69 37695 70 40256 71 43232 72 46375 73 49451 74 53044 75 56767 76 60430 77 64695 78 69142 79 73490 80 78525 81 83768 82 88956 83 94887 84 101063 85 107169 86 114176 87 121388 88 128563 89 136781 90 145266 91 153632 92 163211 93 173108 94 182957 95 194072 96 205560 97 217027 98 230005 99 243287 100 256581 101 271579 102 287010 103 302398 104 319724 105 337501 106 355330 107 375240 108 395702 109 416260 110 439228 111 462664 112 486257 113 512591 114 539561 115 566556 116 596639 117 627462 118 658508 119 692822 120 727937 121 763364 122 802583 123 842517 124 882894 125 927460 126 972985 127 1018841 128 1069418 129 1121090 130 1173308 131 1230503 132 1288991 133 1348206 134 1413074 135 1479066 136 1546013 137 1619269 138 1693999 139 1769561 140 1852104 141 1936257 142 2021676 143 2114540 144 2209242 145 2305407 146 2409973 147 2516250 148 2624361 149 2741756 150 2861228 151 2982459 152 3113998 153 3247927 154 3384143 155 3531189 156 3680992 157 3833485 158 3998199 159 4165517 160 4335953 161 4519788 162 4706834 163 4897076 164 5102064 165 5310540 166 5523021 167 5751153 168 5983286 169 6220015 170 6474109 171 6732050 172 6995402 173 7277847 174 7564892 175 7857325 176 8170685 177 8489237 178 8814339 179 9161605 180 9514675 181 9875155 182 10260225 183 10651077 184 11050384 185 11476401 186 11909283 187 12350981 188 12821909 189 13300352 190 13789114 191 14308855 192 14837118 193 15377020 194 15951031 195 16533434 196 17129048 197 17761743 198 18404386 199 19060768 200 19757410 201 20465016 202 21188595 203 21954910 204 22733373 205 23529506 206 24372585 207 25228048 208 26103408 209 27029589 210 27969887 211 28931059 212 29947499 213 30979582 214 32035449 215 33149711 216 34281381 217 35439445 218 36661384 219 37901120 220 39170023 221 40507918 222 41866336 223 43255615 224 44719387 225 46205494 226 47726584 227 49326673 228 50951545 229 52614770 230 54363908 231 56138545 232 57955665 233 59865639 234 61804403 235 63787857 236 65871526 237 67986866 238 70152302 239 72423627 240 74729713 241 77090750 242 79566849 243 82079201 244 84651832 245 87347927 246 90084841 247 92885775 248 95819729 249 98798087 250 101847360 251 105037394 252 108276291 253 111592718 254 115061403 255 118580822 256 122185094 257 125953020 258 129777653 259 133692088 260 137782027 261 141933778 262 146184999 263 150622004 264 155126369 265 159738539 266 164551246 267 169434594 268 174435738 269 179651610 270 184945623 271 190364635 272 196014055 273 201748502 274 207619775 275 213734576 276 219942083 277 226298063 278 232916491 279 239632161 280 246508690 281 253665897 282 260930663 283 268366341 284 276102095 285 283954049 286 291992981 287 300349333 288 308831981 289 317516604 290 326541881 291 335700337 292 345077477 293 354818559 294 364705589 295 374824422 296 385332160 297 395997954 298 406916246 299 418245184 300 429744939 301 441516863 302 453729433 303 466122498 304 478808949 305 491964911 306 505318292 307 518983348 308 533149313 309 547527668 310 562243873 311 577489365 312 592964550 313 608803233 314 625207961 315 641854964 316 658893208 317 676534699 318 694440384 319 712760654 320 731722935 321 750969700 322 770664954 323 791038460 324 811718130 325 832878477 326 854763819 327 876973322 328 899698688 329 923194588 330 947042046 331 971436993 332 996651556 333 1022244255 334 1048426935 335 1075473960 336 1102927552 337 1131013276 338 1160021425 339 1189459214 340 1219573571 341 1250667821 342 1282227916 343 1314505197 344 1347822327 345 1381638941 346 1416227010 347 1451912409 348 1488133674 349 1525179390 350 1563393450 351 1602174469 352 1641837520 353 1682740645 354 1724255014 355 1766702977 356 1810466586 357 1854885184 358 1900305870 359 1947113170 360 1994621363 361 2043199305 362 2093252519 363 2144047624 364 2195983198 365 2249482045 366 2303780429 367 2359286476 368 2416449154 369 2474466326 370 2533775571 371 2594830646 372 2656799519 373 2720145672 374 2785345947 375 2851512223 376 2919146168 377 2988743956 378 3059379736 379 3131567246 380 3205832849 381 3281207277 382 3358240199 383 3437461952 384 3517866280 385 3600035046 386 3684525852 387 3770268577 388 3857888238 389 3947963577 390 4039380559 391 4132781795 392 4228780079 393 4326209133 394 4425753892 395 4528032038 396 4631835351 397 4737887825 398 4846836967 399 4957397397 400 5070346112 401 5186357246 402 5304092563 403 5424351488 404 5547844272 405 5673172544 406 5801188601 407 5932607778 408 6065980556 409 6202204893 410 6342030655 411 6483921558 412 6628838306 413 6777558624 414 6928483142 415 7082601413 416 7240734813 417 7401213254 418 7565086368 419 7733181348 420 7903767704 421 8077953297 422 8256604362 423 8437887731 424 8622983286 425 8812789562 426 9005402325 427 9202037560 428 9403640708 429 9608224222 430 9817077369 431 10031153022 432 10248393252 433 10470154665 434 10697430867 435 10928047934 436 11163450435 437 11404668118 438 11649442023 439 11899260151 440 12155205000 441 12414923147 442 12679989580 443 12951494385 444 13226997942 445 13508157337 446 13796112362 447 14088288057 448 14386442905 449 14691755277 450 15001552993 451 15317651475 452 15641286902 453 15969675740 454 16304734457 455 16647707993 456 16995715856 457 17350772480 458 17714174592 459 18082885707 460 18459039346 461 18843978837 462 19234554326 463 19632965758 464 20040620258 465 20454240364 466 20876148516 467 21307760472 468 21745683148 469 22192352586 470 22649244824 471 23112790936 472 23585565401 473 24069093778 474 24559673375 475 25059963223 476 25571560034 477 26090615409 478 26619929538 479 27161105158 480 27710162414 481 28270038812 482 28842402386 483 29423070166 484 30015139524 485 30620335393 486 31234324940 487 31860305711 488 32500077850 489 33149138155 490 33810851731 491 34487030522 492 35173016822 493 35872335721 494 36586868522 495 37311727096 496 38050627623 497 38805511593 498 39571314682 499 40351874117 500 41149215412