1 0
2 0
3 0
4 0
5 1
6 0
7 1
8 3
9 1
10 3
11 7
12 3
13 8
14 14
15 8
16 17
17 26
18 18
19 33
20 47
21 36
22 61
23 81
24 68
25 106
26 137
27 121
28 181
29 224
30 209
31 296
32 362
33 347
34 478
35 570
36 565
37 750
38 890
39 894
40 1166
41 1360
42 1396
43 1774
44 2062
45 2134
46 2677
47 3076
48 3228
49 3973
50 4555
51 4804
52 5854
53 6657
54 7085
55 8513
56 9664
57 10315
58 12299
59 13877
60 14903
61 17579
62 19805
63 21305
64 24975
65 28008
66 30252
67 35168
68 39385
69 42580
70 49247
71 54954
72 59570
73 68444
74 76278
75 82719
76 94639
77 105166
78 114242
79 130009
80 144297
81 156759
82 177759
83 196825
84 214044
85 241664
86 267278
87 290613
88 327116
89 361060
90 392802
91 440551
92 485736
93 528269
94 590934
95 650418
96 707533
97 789071
98 867599
99 943381
100 1049707
101 1152431
102 1253082
103 1390735
104 1525321
105 1657719
106 1836152
107 2011146
108 2185330
109 2415219
110 2642907
111 2870260
112 3166610
113 3460964
114 3757595
115 4137628
116 4518181
117 4902652
118 5390025
119 5879334
120 6377261
121 6999464
122 7628344
123 8269619
124 9063683
125 9868141
126 10693143
127 11702534
128 12730816
129 13787123
130 15069423
131 16378407
132 17729177
133 19352477
134 21017154
135 22737319
136 24790578
137 26899946
138 29087529
139 31676522
140 34346328
141 37118232
142 40379503
143 43747783
144 47255024
145 51351608
146 55595811
147 60019169
148 65159353
149 70491828
150 76062365
151 82495562
152 89186595
153 96181584
154 104223623
155 112597407
156 121368030
157 131397815
158 141863468
159 152831805
160 165325424
161 178374375
162 192070770
163 207600069
164 223847867
165 240910285
166 260188885
167 280375482
168 301599993
169 325485518
170 350531714
171 376876166
172 406432470
173 437445391
174 470097763
175 506603438
176 544952860
177 585342304
178 630374936
179 677707464
180 727596909
181 783051938
182 841394363
183 902903538
184 971108447
185 1042895843
186 1118626926
187 1202376418
188 1290592321
189 1383671633
190 1486382670
191 1594608741
192 1708857524
193 1834629470
194 1967235883
195 2107240468
196 2261065844
197 2423293637
198 2594637722
199 2782499961
200 2980719888
201 3190097403
202 3419257546
203 3661101083
204 3916632419
205 4195782509
206 4490494139
207 4801901838
208 5141555319
209 5500194923
210 5879234581
211 6291960842
212 6727883471
213 7188610871
214 7689567156
215 8218728931
216 8778087356
217 9385370586
218 10026982363
219 10705201529
220 11440573119
221 12217555025
222 13038951730
223 13928357218
224 14868229393
225 15861794496
226 16936351392
227 18071900106
228 19272390053
229 20569145562
230 21939636916
231 23388427089
232 24951704159
233 26603849213
234 28350421421
235 30232912154
236 32222520121
237 34325690842
238 36590289705
239 38983652867
240 41513599281
241 44234966743
242 47111111056
243 50151123410
244 53418181167
245 56870837072
246 60520076371
247 64438225812
248 68578889815
249 72954869158
250 77649384835
251 82610103767
252 87852438305
253 93471594015
254 99409125892
255 105683023154
256 112402702179
257 119502424441
258 127003778080
259 135031851287
260 143513409392
261 152473679452
262 162056261475
263 172179023303
264 182872147009
265 194299693901
266 206370408512
267 219119587410
268 232735375402
269 247115745799
270 262302808884
271 278511384758
272 295628437927
273 313703234959
274 332981890618
275 353338441555
276 374831510282
277 397741940118
278 421930612384
279 447466120419
280 474669927051
281 503387549024
282 533700404872
283 565975112643
284 600041644195
285 635995254680
286 674255229641
287 714633488560
288 757242834947
289 802561196637
290 850382366646
291 900838276298
292 954475075737
293 1011065635399
294 1070765850303
295 1134197943358
296 1201113986159
297 1271696219488
298 1346655156798
299 1425719023469
300 1509102716879
301 1597615332270
302 1690961707535
303 1789392900894
304 1893832172078
305 2003957752807
306 2120065108658
307 2243205126846
308 2373030427618
309 2509885943016
310 2654970063707
311 2807906550321
312 2969100588996
313 3139915651879
314 3319948461350
315 3509671654194
316 3710639138842
317 3922417552428
318 4145561105623
319 4381837053369
320 4630785009224
321 4893050873400
322 5170647593983
323 5463085272187
324 5771119998081
325 6097040224283
326 6440331423417
327 6801873954590
328 7184273045079
329 7586988141309
330 8011048113077
331 8459413694543
332 8931525823420
333 9428581312556
334 9953949063069
335 10507051972916
336 11089286566127
337 11704480162185
338 12352048891963
339 13033615620248
340 13753533282413
341 14511214686355
342 15308550664521
343 16150484879084
344 17036443380990
345 17968621235765
346 18952638584612
347 19987942700938
348 21077087413438
349 22226453601836
350 23435533718407
351 24707289471686
352 26048971913488
353 27460133358582
354 28944214797087
355 30509446364935
356 32155474427362
357 33886285452779
358 35711228315347
359 37630067805570
360 39647429309042
361 41773921060181
362 44009474522760
363 46359442823464
364 48835871771770
365 51438897647646
366 54174723510473
367 57057014117381
368 60086178008300
369 63269386884609
370 66622151860363
371 70145211170625
372 73846864821698
373 77744703980369
374 81839890073755
375 86142009484302
376 90671023586890
377 95428601167169
378 100425823420250
379 105685322751043
380 111209403972208
381 117010852870087
382 123115343045529
383 129525936195773
384 136257394541573
385 143338819744745
386 150774206308408
387 158580570422414
388 166790913971247
389 175410335079888
390 184458458075163
391 193972682129443
392 203959448112658
393 214441354601933
394 225460800196301
395 237025806880415
396 249162408397690
397 261918640863110
398 275304430685806
399 289349728432331
400 304108975445165
401 319594331719160
402 335840263796373
403 352908436656416
404 370813678905245
405 389595605113979
406 409324082441771
407 430017058631759
408 451720074213439
409 474512247313686
410 498415227560242
411 523481308863180
412 549800107197357
413 577397586054180
414 606333801553057
415 636710210399073
416 668557867382566
417 701945671551121
418 736988508586323
419 773723350403514
420 812229245630743
421 852636226930961
422 894988216572412
423 939375821271433
424 985946242964976
425 1034751462219575
426 1085895334128459
427 1139544425992318
428 1195760144999417
429 1254661426558050
430 1316436777210695
431 1381158509551061
432 1448962823112392
433 1520062968576892
434 1594543970042028
435 1672561669137830
436 1754357335115435
437 1840030668183469
438 1929759969925997
439 2023818107695353
440 2122321834338216
441 2225474992324777
442 2333586210750589
443 2446791894192748
444 2565325057389968
445 2689534655524904
446 2819579862871093
447 2955726850893969
448 3098370192475946
449 3247695256921749
450 3404006046259913
451 3567748566392338
452 3739138461068195
453 3918522706834974
454 4106405464131172
455 4303037149526729
456 4508813722016464
457 4724304899640691
458 4949801195144898
459 5185754179650003
460 5432807661756082
461 5691298138776542
462 5961740507036401
463 6244862082246022
464 6541052275626906
465 6850897839304182
466 7175220422244759
467 7514470034282577
468 7869315173090565
469 8240683788676708
470 8629095487966032
471 9035311473415445
472 9460379723211843
473 9904899442178608
474 10369737202428322
475 10856076207975802
476 11364606920633055
477 11896315339915670
478 12452537290027862
479 13034067470455875
480 13642027506759566
481 14277925126523772
482 14942674340681045
483 15637550406320408
484 16364254981164373
485 17123838194319248
486 17917749627387114
487 18747909314935973
488 19615522952502150
489 20522237474679040
490 21470219166807475
491 22460851000470572
492 23496003665408659
493 24578120664787671
494 25708787288726745
495 26890127393358990
496 28124896948446176
497 29414911543345139
498 30762581846520877
499 32171015488056278
500 33642290541000182
501 35179141997677725
502 36785073691677240
503 38462462167181903
504 40214409566466832
505 42044865491005001
506 43956546243538986
507 45952968894919662
508 48038585062102729
509 50216496999044406
510 52490691151977352
511 54866183779902388
512 57346515959460932
513 59936204288475235
514 62640900643208492
515 65464644101473860
516 68412550552857470
517 71490986555604106
518 74704556778908501
519 78059053614792433
520 81561647795571535
521 85217585258083235
522 89033422594553932
523 93017234445036213
524 97174994278088010
525 101514120852473591
526 106043705470374299
527 110770545735605322
528 115703033683346498
529 120851402977964966
530 126223385280201453
531 131828470050733677
532 137678175270712960
533 143781289767940822
534 150148541042705539
535 156792889686681404
536 163724321545732481
537 170954959300239202
538 178499384730992364
539 186368937337154125
540 194577312734817947
541 203140913065148578
542 212072609143693631
543 221387868186993947
544 231105137172899955
545 241239017211428168
546 251806971581163727
547 262829742490978026
548 274323886716003999
549 286309114468380949
550 298808745136980128
551 311841543547585114
552 325429749979277943
553 339599575527726806
554 354372278554846072
555 369772945844970654
556 385831034057354782
557 402570614750349418
558 420019977973802059
559 438212220704701186
560 457174588836644731
561 476938974381830786
562 497542558386700365
563 519016165374790351
564 541395738380449978
565 564723037550542590
566 589032922268450325
567 614365888379556742
568 640768831172322689
569 668281155525582534
570 696948474746781877
571 726823439528496185
572 757950575854401230
573 790381245352462972
574 824174550308855988
575 859380781900210789
576 896057759342658182
577 934271813044173709
578 974079724679521969
579 1015546563341390486
580 1058746758525356653
581 1103744393770451666
582 1150612678066463571
583 1199435111353002814
584 1250283991834114858
585 1303241662388107802
586 1358401782147479989
587 1415845884782350881
588 1475666562780190596
589 1537968848528754250
590 1602844658541647629
591 1670398080683574604
592 1740746880498819904
593 1813994640065787694
594 1890258339901999958
595 1969669994870923008
596 2052346293150904422
597 2138418667658535972
598 2228035079805516877
599 2321326933788806712
600 2418441863100926435
601 2519545667586012511
602 2624786273969049563
603 2734329467239257115
604 2848361002218272903
605 2967047346379920643
606 3090574621307509305
607 3219150895588259998
608 3352963440350249549
609 3492221151585897056
610 3637157049007633691
611 3787981734591488790
612 3944929607363108798
613 4108261576693833296
614 4278214406883416203
615 4455051043282526967
616 4639063568647627661
617 4830518070604553992
618 5029709444984351238
619 5236964605742943478
620 5452582502905622427
621 5676893778329875627
622 5910264262447402064
623 6153029717148120025
624 6405560773315071444
625 6668266727357286274
626 6941524571847085863
627 7225749656012758979
628 7521399820725477420
629 7828898218583972495
630 8148710200878156219
631 8481347806985328566
632 8827285861052641731
633 9187045603818078618
634 9561199581381265803
635 9950280435359465135
636 10354871869701474186
637 10775613958405155310
638 11213104027994422580
639 11667995567995106957
640 12141004009915763937
641 12632799020116342486
642 13144112045192851523
643 13675742586167256748
644 14228441197614720120
645 14803026382141106640
646 15400391420678291907
647 16021377280916367627
648 16666899670079241624
649 17337956450553217471
650 18035489633477746817
651 18760523427244613196
652 19514172309375262255
653 20297491174495915255
654 21111625325303462771
655 21957819236290845161
656 22837253892194518121
657 23751209702711557592
658 24701076040695271126
659 25688174684711087391
660 26713936764529561071
661 27779913117068624707
662 28887582706489568920
663 30038544749576893097
664 31234529985735631155
665 32477192807477359439
666 33768319859399585178
667 35109842274755679350
668 36503610200596040709
669 37951619215131431820
670 39456023643193633843
671 41018891998950525784
672 42642452732698601946
673 44329108688845371316
674 46081171930615369279
675 47901130389067677161
676 49791663594656493012
677 51755355163224049744
678 53794982111167219314
679 55913531937561149727
680 58113890980522042125
681 60399158236864458998
682 62772663947788957966
683 65237631822364741675
684 67797519419693824284
685 70456038331180930869
686 73216788183869158133
687 76083625732542965811
688 79060686817295138574
689 82151989815980190788
690 85361835846126681198
691 88694832610056095024
692 92155464865461094938
693 95748528244142277213
694 99479155193541482145
695 103352349755371011814
696 107373457798227467532
697 111548195190858629597
698 115882144059437249229
699 120381262359172705004
700 125051914523539673914
701 129900326050989976193
702 134933135673860943534
703 140157428646521552383
704 145580146370616345872
705 151208684572294957948
706 157050929515013530976
707 163114619006063300132
708 169407990375815276145
709 175939819811228698795
710 182718730918531415978
711 189753896479916626959
712 197055081242243306086
713 204631893791217320073
714 212494546500415294330
715 220653902010841695591
716 229120663973463095897
717 237906199821280486109
718 247022591331504660893
719 256481759313042174810
720 266296354336881708480
721 276479811663941898604
722 287045404719878486714
723 298007209174927988108
724 309380162696523018378
725 321179041504193383611
726 333419503769211891091
727 346118154531697527251
728 359291439352501349384
729 372956773305811669244
730 387132611599035740137
731 401837253709824985352
732 417090064909596045852
733 432911552993640815411
734 449322075967074623189
735 466343163395009611687
736 483997599874376602826
737 502308028613558665212
738 521298380667880148687
739 540993965641510055006
740 561419963124798271475
741 582602968295831279853
742 604571090593615998856
743 627352324155156328281
744 650976219139229898265
745 675473988955864059173
746 700876750398985906912
747 727217330545821924015
748 754530383413091230776
749 782850489541719355212
750 812214109329572797127
751 842659709814758558653
752 874225712946771705758
753 906952606795284266356
754 940883083483248781612
755 976059824305779291053
756 1012527781409742564449
757 1050334327714752747537
758 1089526866431027204634
759 1130155296491915630188
760 1172272175664987559026
761 1215930140794725717626
762 1261184571591411434313
763 1308093767934676108163
764 1356716166455090653475
765 1407113218089546736494
766 1459349580991163554668
767 1513490117665057751343
768 1569603003215549866179
769 1627759935060740683794
770 1688032894008353716613
771 1750497501065798131796
772 1815233245623046407958
773 1882319992258353532903
774 1951841605719522397754
775 2023886199007032464036
776 2098542366734301184940
777 2175903098995936767385
778 2256066051309485768087
779 2339129483534385658192
780 2425196485334725594975
781 2514375269690063444957
782 2606774795255542504977
783 2702509327422199678768
784 2801698757703176159093
785 2904463885341804399311
786 3010931340255621180287
787 3121233930340315534087
788 3235505556830597780539
789 3353886526928152486136
790 3476523931740564204596
791 3603566167534175380655
792 3735168668463011839690
793 3871494317580449773632
794 4012707544613782732671
795 4158980510979036072964
796 4310493557068027716201
797 4467428844479452807841
798 4629977028503381206547
799 4798337744592464482724
800 4972712761236349183086
801 5153313177162084335553
802 5340359950765697801577
803 5534076526748005516500
804 5734696598713495286065
805 5942464685031890060234
806 6157628190331540557778
807 6380445776583407864753
808 6611187989846748809337
809 6850128714223378654621
810 7097554198450542238609
811 7353763737668074117947
812 7619060475100762471135
813 7893761133983945203919
814 8178196759607701326018
815 8472702820020646121324
816 8777629697622582992183
817 9093343496417864902901
818 9420215390337867771471
819 9758632932093830537567
820 10109000931842576637414
821 10471729997205849031323
822 10847248722143238278604
823 11236004642908201406163
824 11638451910734208599685
825 12055064427277647870364
826 12486336885188066270889
827 12932771509294480417813
828 13394892211086081324488
829 13873245720899889890957
830 14368387329861011484409
831 14880896140273699926363
832 15411376298076034855227
833 15960441661952195959342
834 16528732233284110602701
835 17116915497214812547896
836 17725669941232762506210
837 18355702753450149762227
838 19007751282492885071926
839 19682565321230309507569
840 20380926169907814772073
841 21103648224796864553538
842 21851559938010835142604
843 22625524347957671204404
844 23426440808823557533601
845 24255224529894577381885
846 25112828684682728045541
847 26000246293069155188266
848 26918488238118067671021
849 27868607072117738138680
850 28851699065652797776915
851 29868880591365155063017
852 30921313755327774129053
853 32010208627121597356851
854 33136797873766985162784
855 34302364352834148052675
856 35508243540392889320827
857 36755796288665138552113
858 38046438528926599064874
859 39381643914078492317235
860 40762914566432638104642
861 42191813047712692655429
862 43669965236191721247638
863 45199028920060461872582
864 46780728205174477861724
865 48416856646683528190294
866 50109243535262690736632
867 51859790923969019326718
868 53670477037946848278718
869 55543320088388339420869
870 57480418115131840694469
871 59483952698142939497918
872 61556150124728579860085
873 63699324256915392591275
874 65915880572599457083262
875 68208274497488516346883
876 70579057523776287255439
877 73030881609142889514181
878 75566454474228754636145
879 78188589213475225091429
880 80900209084968820587118
881 83704299558358145638879
882 86603961678736573149633
883 89602417280834527473000
884 92702957560114810604731
885 95909000467174274546293
886 99224096385314267968766
887 102651872979584349261302
888 106196096922077652906440
889 109860680072702040933580
890 113649620347063397745213
891 117567068092220907140494
892 121617332816834773927763
893 125804819798484298497325
894 130134101455656561739828
895 134609924674592541438784
896 139237142860831775400729
897 144020792675385197208294
898 148966102012913374548973
899 154078417179375954356880
900 159363285390333536696785
901 164826463456678789671924
902 170473839752292865778332
903 176311522898038978545143
904 182345851219690650377767
905 188583309143646278454960
906 195030622524504421085016
907 201694768941967345897355
908 208582888142239366346995
909 215702384496655295555681
910 223060938214051114166025
911 230666409416327568016233
912 238526948254889080685662
913 246651007117781826460333
914 255047237904720240041012
915 263724610362240494350618
916 272692425376118524430874
917 281960204978324709625197
918 291537819506756072438604
919 301435502077083549349372
920 311663730827814429951379
921 322233365549871581209941
922 333155663444973632232158
923 344442153078025856868346
924 356104781173268304260071
925 368155929770942359234146
926 380608281326461665860982
927 393474976415308252537839
928 406769632414719986758267
929 420506199147522474498716
930 434699128296837357791663
931 449363393745409700311355
932 464514337128306349614331
933 480167849810925828812031
934 496340395035925155186150
935 513048842702271368636100
936 530310664827433006503765
937 548143959659250657551727
938 566567274960778775050227
939 585599817937984047022036
940 605261481493993034017867
941 625572655246702775511009
942 646554450980437210010514
943 668228731229207995991665
944 690617907211132551200519
945 713745180932174667914563
946 737634576308347605975870
947 762310723142128350868643
948 787799117094678098509765
949 814126153568316907120377
950 841318896801724737203312
951 869405359007332820540908
952 898414537262429075359834
953 928376166733979846820317
954 959321020378909564700454
955 991280949106246569156769
956 1024288618087919407345270
957 1058377828512156730610238
958 1093583561310474040384164
959 1129941695436950896864023
960 1167489353280614208464963
961 1206264948268306731757884
962 1246307883933707408004705
963 1287658924701133125905015
964 1330360247711812397156086
965 1374455121421315844415833
966 1419988303599564726159961
967 1467006097749105851995331
968 1515556009900866995151746
969 1565687175797903098214951
970 1617450422316698803536928
971 1670897901038887086633377
972 1726083546737765288862366
973 1783063144239320649275093
974 1841893937270481668199943
975 1902635120508779121425353
976 1965347912369170871035834
977 2030095137526423824096957
978 2096941754961724625483641
979 2165954937192553228672814
980 2237203624780533231554204
981 2310759092971533780700951
982 2386695037943347947385902
983 2465087101495585365124722
984 2546013479078351544909241
985 2629555013670242185933396
986 2715794688750458537996271
987 2804818280698492771010890
988 2896714460981958669633802
989 2991574255383371936936728
990 3089491743980583391162170
991 3190564172369581716959720
992 3294891375010844714169133
993 3402576526215903050301909
994 3513726261208376764116245
995 3628450061312823032974893
996 3746861059633083651517046
997 3869076172809807290346652
998 3995215445654965781032644
999 4125402915455824252731968
1000 4259766755378335565256847