0 1
1 1
2 1
3 2
4 3
5 5
6 6
7 9
8 11
9 14
10 17
11 22
12 26
13 32
14 37
15 42
16 50
17 59
18 69
19 80
20 91
21 101
22 115
23 133
24 152
25 170
26 190
27 210
28 235
29 265
30 300
31 334
32 366
33 398
34 441
35 484
36 541
37 597
38 648
39 703
40 770
41 848
42 935
43 1022
44 1102
45 1184
46 1281
47 1406
48 1534
49 1661
50 1789
51 1916
52 2062
53 2244
54 2435
55 2620
56 2804
57 2997
58 3210
59 3473
60 3763
61 4042
62 4300
63 4571
64 4883
65 5237
66 5641
67 6043
68 6409
69 6799
70 7257
71 7777
72 8322
73 8887
74 9406
75 9936
76 10553
77 11258
78 12027
79 12800
80 13535
81 14286
82 15115
83 16102
84 17164
85 18170
86 19164
87 20194
88 21327
89 22655
90 24103
91 25474
92 26806
93 28188
94 29715
95 31444
96 33317
97 35195
98 36989
99 38812
100 40889
101 43221
102 45687
103 48172
104 50530
105 52892
106 55580
107 58672
108 61894
109 65129
110 68287
111 71458
112 74969
113 78968
114 83181
115 87315
116 91354
117 95508
118 100054
119 105147
120 110691
121 116107
122 121281
123 126658
124 132517
125 139002
126 146060
127 153017
128 159681
129 166547
130 174181
131 182577
132 191455
133 200276
134 208837
135 217495
136 227062
137 237796
138 249004
139 260232
140 271276
141 282353
142 294407
143 307897
144 322062
145 336053
146 349781
147 363790
148 378982
149 395902
150 413859
151 431562
152 448741
153 466364
154 485556
155 506434
156 528608
157 550845
158 572297
159 594327
160 618332
161 644460
162 671937
163 699526
164 726282
165 753402
166 782940
167 815517
168 849639
169 883623
170 917087
171 950996
172 987375
173 1027562
174 1069561
175 1110997
176 1152059
177 1194026
178 1238869
179 1288096
180 1340017
181 1391444
182 1441882
183 1493361
184 1548532
185 1608328
186 1671394
187 1734489
188 1796078
189 1858919
190 1926883
191 2000336
192 2076891
193 2153889
194 2229155
195 2305469
196 2387950
197 2477380
198 2570520
199 2663972
200 2756109
201 2849587
202 2949318
203 3057486
204 3170564
205 3283036
206 3394187
207 3507746
208 3628491
209 3759177
210 3896707
211 4033198
212 4167281
213 4304634
214 4450538
215 4607380
216 4771749
217 4936195
218 5098144
219 5263367
220 5439956
221 5629284
222 5826219
223 6024107
224 6219241
225 6416927
226 6627801
227 6855277
228 7091191
229 7327999
230 7562827
231 7800448
232 8052744
233 8324578
234 8606757
235 8888535
236 9168061
237 9453203
238 9755003
239 10078544
240 10416291
241 10753659
242 11086796
243 11427020
244 11786682
245 12169665
246 12570026
247 12971709
248 13368130
249 13772686
250 14201688
251 14658562
252 15133292
253 15609624
254 16080976
255 16559697
256 17066806
257 17608900
258 18170221
259 18733442
260 19294206
261 19863236
262 20462804
263 21103340
264 21767094
265 22431208
266 23092791
267 23766172
268 24474524
269 25229625
270 26014600
271 26800334
272 27579448
273 28373224
274 29209407
275 30095523
276 31016301
277 31942338
278 32859735
279 33794713
280 34781766
281 35825877
282 36906434
283 37994298
284 39073625
285 40169907
286 41325521
287 42550522
288 43817852
289 45092400
290 46361913
291 47651746
292 49004304
293 50439726
294 51925052
295 53412598
296 54896462
297 56408156
298 57991199
299 59667838
300 61406091
301 63147631
302 64881367
303 66648808
304 68499175
305 70451516
306 72474204
307 74509020
308 76534299
309 78595257
310 80758180
311 83037810
312 85391504
313 87762153
314 90122131
315 92517792
316 95031519
317 97684986
318 100421455
319 103176215
320 105927256
321 108721173
322 111643069
323 114723871
324 117902787
325 121096105
326 124286035
327 127534467
328 130924755
329 134494262
330 138187480
331 141896278
332 145593906
333 149361667
334 153293058
335 157421606
336 161690582
337 165986809
338 170270877
339 174632533
340 179190565
341 183973268
342 188902812
343 193868098
344 198826562
345 203863094
346 209122361
347 214649201
348 220339483
349 226072290
350 231810592
351 237635365
352 243703678
353 250078130
354 256641732
355 263242931
356 269849908
357 276570788
358 283566980
359 290905157
360 298473110
361 306085308
362 313692185
363 321436100
364 329496592
365 337925276
366 346617157
367 355377700
368 364129570
369 373037182
370 382313974
371 392008441
372 401988423
373 412050663
374 422112471
375 432335042
376 442974324
377 454107375
378 465559318
379 477099007
380 488661603
381 500408837
382 512607447
383 525369538
384 538493217
385 551698479
386 564940538
387 578410984
388 592387144
389 606993163
390 622029638
391 637167510
392 652327013
393 667749218
394 683750225
395 700436934
396 717610167
397 734928238
398 752263773
399 769892535
400 788204690
401 807287095
402 826890335
403 846670146
404 866481359
405 886606500
406 907500269
407 929280930
408 951647009
409 974209731
410 996842352
411 1019833801
412 1043653134
413 1068479325
414 1093978827
415 1119669788
416 1145450014
417 1171669792
418 1198812018
419 1227082098
420 1256143919
421 1285419920
422 1314772921
423 1344634605
424 1375539747
425 1407676508
426 1440696491
427 1474003532
428 1507404733
429 1541366909
430 1576540730
431 1613096317
432 1650602132
433 1688459321
434 1726439848
435 1765009752
436 1804940706
437 1846461812
438 1889039953
439 1932010083
440 1975167577
441 2018992728
442 2064308240
443 2111408301
444 2159707499
445 2208410822
446 2257333223
447 2307072539
448 2358464878
449 2411830899
450 2466601608
451 2521830313
452 2577268223
453 2633644493
454 2691874804
455 2752255386
456 2814221573
457 2876767439
458 2939546453
459 3003371443
460 3069325268
461 3137694267
462 3207776039
463 3278523006
464 3349572052
465 3421736911
466 3496278833
467 3573584592
468 3652774676
469 3732711525
470 3813084040
471 3894706736
472 3978918198
473 4066226295
474 4155660234
475 4245886441
476 4336622046
477 4428825225
478 4523904008
479 4622416255
480 4723379378
481 4825247138
482 4927612286
483 5031653233
484 5138938788
485 5249954945
486 5363709631
487 5478582265
488 5594007686
489 5711315232
490 5832317910
491 5957458440
492 6085574825
493 6214981343
494 6345059569
495 6477158350
496 6613356053
497 6754255335
498 6898465578
499 7044104412
500 7190620934
501 7339412854
502 7492657813
503 7651173798
504 7813406616
505 7977130029
506 8141884324
507 8309291813
508 8481625550
509 8659788585
510 8842183707
511 9026273799
512 9211446225
513 9399619002
514 9593297779
515 9793325359
516 9998063649
517 10204865768
518 10412879527
519 10624198555
520 10841776518
521 11066396395
522 11296118517
523 11528218689
524 11761715737
525 11998785747
526 12242823644
527 12494794725
528 12752412387
529 13012669956
530 13274675770
531 13540700905
532 13814304583
533 14096715162
534 14385448165
535 14677003813
536 14970557940
537 15268769216
538 15575313394
539 15891571404
540 16215048259
541 16541684178
542 16870439060
543 17204439535
544 17547711612
545 17901597118
546 18263486431
547 18629085640
548 18997071178
549 19370859633
550 19755106686
551 20151095673
552 20555737234
553 20964609596
554 21376280462
555 21794212161
556 22223718914
557 22666419672
558 23118650550
559 23575614607
560 24035967884
561 24503259568
562 24983169273
563 25477709896
564 25982868673
565 26493123926
566 27007179571
567 27529210861
568 28065165165
569 28617194384
570 29181233642
571 29750979595
572 30324792326
573 30907584489
574 31505818370
575 32121506799
576 32750511821
577 33386176834
578 34026361184
579 34676486695
580 35343890563
581 36030560811
582 36731731696
583 37440397941
584 38154264361
585 38878897055
586 39622604496
587 40387897713
588 41169132230
589 41958642660
590 42754346229
591 43562008319
592 44390413705
593 45242697111
594 46112640564
595 46991511919
596 47877422239
597 48776907048
598 49699194770
599 50647708737
600 51616048525
601 52594430969
602 53580368681
603 54581421553
604 55607732307
605 56662550513
606 57739272240
607 58827575708
608 59924231027
609 61037571606
610 62179170346
611 63352122434
612 64548856137
613 65758616585
614 66977856875
615 68215258039
616 69483780233
617 70787147956
618 72116671754
619 73460589708
620 74815587848
621 76190717591
622 77599594642
623 79046932072
624 80523287206
625 82015175649
626 83519509907
627 85046585812
628 86610674550
629 88216989657
630 89855746005
631 91511727893
632 93181198635
633 94875978021
634 96611581969
635 98393090891
636 100210259397
637 102047118942
638 103899027897
639 105778746370
640 107703895967
641 109679456269
642 111693711972
643 113730102960
644 115783430560
645 117866881906
646 120000315677
647 122189642703
648 124421408847
649 126677607187
650 128953257499
651 131262209279
652 133625535692
653 136050318536
654 138521945770
655 141020077859
656 143539902972
657 146097257153
658 148714120535
659 151398130881
660 154134400131
661 156900030077
662 159689191271
663 162519963877
664 165416132731
665 168385251909
666 171411879079
667 174471747393
668 177557662346
669 180689317653
670 183893441201
671 187177602993
672 190524175639
673 193907685090
674 197320476694
675 200782906837
676 204324818634
677 207955254192
678 211653864078
679 215393202120
680 219166071712
681 222993576714
682 226907404963
683 230918386650
684 235004425211
685 239134765392
686 243302374727
687 247530979598
688 251853980032
689 256283093386
690 260795495408
691 265356912451
692 269958667412
693 274627873764
694 279400841939
695 284288881890
696 289268304722
697 294302907950
698 299382016360
699 304535281247
700 309803132774
701 315196725782
702 320689545339
703 326243581648
704 331847311802
705 337531550427
706 343341075404
707 349289226297
708 355345945246
709 361469911309
710 367650134558
711 373918896466
712 380323560875
713 386880224131
714 393556107073
715 400304809330
716 407115997895
717 414025706565
718 421083722780
719 428307536820
720 435662985239
721 443098847990
722 450602724804
723 458215110434
724 465990013550
725 473944648166
726 482043405443
727 490232351573
728 498496171297
729 506878657123
730 515440260127
731 524198074198
732 533112137238
733 542126035788
734 551222911588
735 560448645210
736 569870264817
737 579507412347
738 589315129049
739 599232375537
740 609242927423
741 619395052648
742 629759458286
743 640359347583
744 651146237294
745 662052022268
746 673060908817
747 684226793171
748 695623782322
749 707277210729
750 719137000500