0 1
1 0
2 0
3 0
4 1
5 1
6 1
7 1
8 2
9 2
10 3
11 3
12 5
13 5
14 7
15 8
16 11
17 12
18 16
19 18
20 24
21 27
22 34
23 39
24 50
25 57
26 70
27 81
28 100
29 115
30 140
31 161
32 195
33 225
34 269
35 311
36 371
37 427
38 505
39 583
40 688
41 791
42 928
43 1067
44 1248
45 1434
46 1668
47 1914
48 2223
49 2546
50 2945
51 3370
52 3889
53 4443
54 5113
55 5834
56 6698
57 7632
58 8740
59 9946
60 11371
61 12919
62 14735
63 16724
64 19042
65 21581
66 24526
67 27761
68 31499
69 35610
70 40336
71 45543
72 51514
73 58092
74 65606
75 73903
76 83347
77 93775
78 105616
79 118698
80 133517
81 149891
82 168388
83 188838
84 211898
85 237381
86 266051
87 297751
88 333348
89 372691
90 416798
91 465539
92 520095
93 580372
94 647725
95 722129
96 805158
97 896832
98 998992
99 1111771
100 1237284
101 1375774
102 1529723
103 1699526
104 1888067
105 2095937
106 2326475
107 2580547
108 2862055
109 3172131
110 3515342
111 3893233
112 4311104
113 4770964
114 5279023
115 5837867
116 6454745
117 7132958
118 7880956
119 8702934
120 9608786
121 10603699
122 11699272
123 12902010
124 14225429
125 15677557
126 17274243
127 19025353
128 20949442
129 23058586
130 25374474
131 27911869
132 30696188
133 33745294
134 37088964
135 40748903
136 44759902
137 49148157
138 53954453
139 59210307
140 64963470
141 71251798
142 78131144
143 85646939
144 93864567
145 102838255
146 112644538
147 123348239
148 135038802
149 147793422
150 161716779
151 176900637
152 193467402
153 211526040
154 231219551
155 252677188
156 276066072
157 301539076
158 329291457
159 359504037
160 392404685
161 428206837
162 467176556
163 509565454
164 555683947
165 605828368
166 660360627
167 719629408
168 784056658
169 854051882
170 930106803
171 1012702229
172 1102410709
173 1199795998
174 1305524736
175 1420257248
176 1544769241
177 1679833535
178 1826352202
179 1985228955
180 2157512531
181 2344258380
182 2546685166
183 2766025003
184 3003692981
185 3261125977
186 3539966774
187 3841889627
188 4168800564
189 4522649026
190 4905645177
191 5320057238
192 5768447084
193 6253451382
194 6778038160
195 7345270779
196 7958585695
197 8621539146
198 9338108528
199 10112419246
200 10949072284
201 11852850282
202 12829072685
203 13883280536
204 15021621254
205 16250509702
206 17577046627
207 19008654599
208 20553530992
209 22220258530
210 24018296648
211 25957563307
212 28048968724
213 30303967274
214 32735135951
215 35355695861
216 38180138970
217 41223715916
218 44503117190
219 48035925464
220 51841353424
221 55939660445
222 60352952999
223 65104561557
224 70219909865
225 75725850863
226 81651609205
227 88028075771
228 94888829527
229 102269386615
230 110208311229
231 118746417469
232 127927973728
233 137799857717
234 148412863812
235 159820806692
236 172081942057
237 185258018004
238 199415817091
239 214626155762
240 230965558487
241 248515201184
242 267362732664
243 287601161122
244 309330831799
245 332658258799
246 357698274727
247 384572803635
248 413413200166
249 444358964430
250 477560285439
251 513176700887
252 551379863483
253 592352143245
254 636289641608
255 683400738518
256 733909371894
257 788053536027
258 846088853415
259 908287023195
260 974939715612
261 1046356976547
262 1122871471644
263 1204836856512
264 1292632403552
265 1386661341367
266 1487355906556
267 1595175662449
268 1710613009996
269 1834191502378
270 1966471862501
271 2108050301473
272 2259565095617
273 2421694927447
274 2595166072284
275 2780750786608
276 2979275164368
277 3191617590865
278 3418717342476
279 3661573134632
280 3921252530753
281 4198890623385
282 4495700337153
283 4812971273516
284 5152081002329
285 5514494117059
286 5901774609114
287 6315585190805
288 6757700862988
289 7230008557637
290 7734522030584
291 8273381892932
292 8848871954404
293 9463419730313
294 10119614389797
295 10820207818843
296 11568134346098
297 12366512467858
298 13218666529073
299 14128129235399
300 15098665494941
301 16134275842201
302 17239222679529
303 18418034767245
304 19675536104109
305 21016851668213
306 22447439221574
307 23973096486927
308 25599996195194
309 27334694925503
310 29184171731650
311 31155838908781
312 33257584582434
313 35497785677265
314 37885354908258
315 40429756278513
316 43141056928659
317 46029945543918
318 49107789592623
319 52386657040691
320 55879379572432
321 59599578083725
322 63561732520243
323 67781211687861
324 72274350427404
325 77058484319976
326 82152035014383
327 87574550496347
328 93346799434924
329 99490817781244
330 106030013126994
331 112989218454618
332 120394807614970
333 128274757179745
334 136658774237657
335 145578367426046
336 155066988396082
337 165160113194002
338 175895398916875
339 187312776779655
340 199454625601294
341 212365878072097
342 226094212928737
343 240690176069582
344 256207393488180
345 272702709115768
346 290236420773402
347 308872436855459
348 328678537833646
349 349726554097955
350 372092655852099
351 395857554732089
352 421106825182113
353 447931132799649
354 476426590667364
355 506695017657893
356 538844333588142
357 572988851135288
358 609249714056330
359 647755226804603
360 688641340553901
361 732052025017994
362 778139807570276
363 827066192325662
364 879002258147341
365 934129130657345
366 992638645614134
367 1054733880088925
368 1120629888417501
369 1190554299542034
370 1264748133465931
371 1343466472574437
372 1426979367423163
373 1515572590660420
374 1609548641980623
375 1709227594292568
376 1814948208640797
377 1927068883379809
378 2045968891111388
379 2172049442735103
380 2305735059770972
381 2447474766548861
382 2597743612654749
383 2757044008023084
384 2925907411885950
385 3104895827079852
386 3294603673694035
387 3495659460769363
388 3708727864683225
389 3934511598464800
390 4173753717199635
391 4427239707295773
392 4695800043603410
393 4980312523501044
394 5281705102976482
395 5600958503157360
396 5939109355579547
397 6297253111687389
398 6676547530807784
399 7078215926546296
400 7503551034416307
401 7953918632794066
402 8430761831198944
403 8935605107408425
404 9470059061771864
405 10035824916686883
406 10634699787028731
407 11268581693210439
408 11939475403199396
409 12649498015750626
410 13400885435429879
411 14195998588778908
412 15037330600073766
413 15927513709963455
414 16869327226972626
415 17865705225407110
416 18919745355545354
417 20034717405913619
418 21214073063682492
419 22461455435512450
420 23780709859379058
421 25175894488007399
422 26651292264047838
423 28211422681248354
424 29861055046389485
425 31605221545584110
426 33449231929436488
427 35398688025065270
428 37459499995224229
429 39637902451583932
430 41940472454056542
431 44374147397255515
432 46946244933664133
433 49664482822977230
434 52537000981912633
435 55572383506110583
436 58779683070117531
437 62168445353476086
438 65748736037722836
439 69531167892135474
440 73526930640118052
441 77747820986791701
442 82206275654969245
443 86915404666097308
444 91889027877050748
445 97141711857883080
446 102688810294814945
447 108546504843880377
448 114731849802601725
449 121262817357782449
450 128158346969794251
451 135438395475436720
452 143123991674176336
453 151237291794518278
454 159801639821147588
455 168841628885421117
456 178383167927416538
457 188453549628115031
458 199081524060892341
459 210297373846180782
460 222132995512935051
461 234621982626014394
462 247799715651429142
463 261703453882517909
464 276372434683124361
465 291847975122714143
466 308173581559507765
467 325395061986934303
468 343560647015917736
469 362721114035940932
470 382929920762426268
471 404243342427229905
472 426720619173644853
473 450424107613611125
474 475419443481807074
475 501775709030746113
476 529565612496793166
477 558865672952221269
478 589756418290701813
479 622322589317634432
480 656653358133270830
481 692842553420150418
482 730988901289274573
483 771196273919223313
484 813573955135516670
485 858236914770744429
486 905306101472993490
487 954908745391232292
488 1007178680956108779
489 1062256680753653544
490 1120290811292570382
491 1181436801213083800
492 1245858433352843351
493 1313727950748274165
494 1385226488638029697
495 1460544522055866751
496 1539882341768008367
497 1623450547631133720
498 1711470572853237891
499 1804175227700109829
500 1901809276900065732
501 2004630038732845510
502 2112908020870040482
503 2226927580373995244
504 2346987623783614633
505 2473402334091018755
506 2606501941449897355
507 2746633523790916212
508 2894161855150425302
509 3049470287235520665
510 3212961683052468228
511 3385059387443224683
512 3566208254439158596
513 3756875715571142642
514 3957552910190532074
515 4168755861209311811
516 4391026718525749942
517 4624935052785621889
518 4871079223030425286
519 5130087800095590764
520 5402621070671199867
521 5689372603075006780
522 5991070901091102466
523 6308481126082349322
524 6642406915258645214
525 6993692275438029784
526 7363223581802694438
527 7751931660089249200
528 8160793983431420350
529 8590836961368511468
530 9043138354059484688
531 9518829788260488585
532 10019099410037498025
533 10545194649790944777
534 11098425136611792414
535 11680165736537609954
536 12291859753903191919
537 12935022269318301505
538 13611243655775175811
539 14322193245359294899
540 15069623190514677364
541 15855372491253965710
542 16681371234866990504
543 17549645018410600809
544 18462319603297157869
545 19421625771139036088
546 20429904433100740983
547 21489611960771754250
548 22603325793932460630
549 23773750292064560402
550 25003722888294987805
551 26296220511452917066
552 27654366338453256672
553 29081436841505008751
554 30580869196108950108
555 32156269013154560421
556 33811418465070581753
557 35550284768153403831
558 37377029095271051861
559 39296015879885625781
560 41311822590111883514
561 43429249932582341117
562 45653332569648356396
563 47989350308536059210
564 50442839851108789497
565 53019607061728720441
566 55725739847329523335
567 58567621606098271217
568 61551945344696452623
569 64685728419371679039
570 67976328007088905221
571 71431457261040572761
572 75059202263278113178
573 78868039727896876520
574 82866855574570141312
575 87064964325021783939
576 91472129449755434142
577 96098584616883208866
578 100955055978403793163
579 106052785445136644822
580 111403555094235861214
581 117019712659990844678
582 122914198260989587099
583 129100572314004410259
584 135593044797456968696
585 142406505814648285105
586 149556557630060725222
587 157059548128950102077
588 164932605884700619871
589 173193676784423119958
590 181861562409212141659
591 190955960120062323043
592 200497505058631175317
593 210507814014670337699
594 221009531382970976839
595 232026377162800302349
596 243583197237296390421
597 255706015887325557045
598 268422090792919251512
599 281759970478749643244
600 295749554473513012277
601 310422156142107408404
602 325810568478421430152
603 341949132820571964359
604 358873810795634434156
605 376622259459251042818
606 395233909957759346057
607 414750049682430123068
608 435213908265543662496
609 456670747392822976136
610 479167954805633267560
611 502755142473213422218
612 527484249333740578596
613 553409648591139689406
614 580588259993685839549
615 609079667088948254542
616 638946239910359639836
617 670253263098706704194
618 703069069945199321754
619 737465182369377749818
620 773516457352206153105
621 811301239848914572086
622 850901522738115125566
623 892403113844548004254
624 935895810630835807212
625 981473582610028374645
626 1029234762116067363514
627 1079282243500171792883
628 1131723691435138247990
629 1186671758413764285040
630 1244244312171604665173
631 1304564673140650209797
632 1367761862715985107029
633 1433970862464777080464
634 1503332885115405687855
635 1575995657481480622966
636 1652113716218509007592
637 1731848716596238143512
638 1815369755248938901720
639 1902853707118078648880
640 1994485577619054105466
641 2090458870281324253175
642 2190975970968297885871
643 2296248548964992260863
644 2406497976120217351064
645 2521955764374116095057
646 2642864022944369041492
647 2769475935549254175156
648 2902056259034059136948
649 3040881843831355331335
650 3186242177722001896987
651 3338439953385119527080
652 3497791661312010486057
653 3664628208635931323107
654 3839295565569147667431
655 4022155440069310604273
656 4213585982552068914638
657 4413982521349142279158
658 4623758330863989065672
659 4843345433209199120207
660 5073195435423466834056
661 5313780403145585413416
662 5565593773000403921580
663 5829151304676654925290
664 6104992075120934828617
665 6393679515940220733232
666 6695802496619769820663
667 7011976454772149094382
668 7342844576221113229222
669 7689079026271295703280
670 8051382235179734692004
671 8430488239328353335011
672 8827164081342376462320
673 9242211270816024158898
674 9676467309137444048751
675 10130807280251742841711
676 10606145511120499676043
677 11103437303910822642268
678 11623680743959738115803
679 12167918585759298186436
680 12737240221318303353469
681 13332783733378050101403
682 13955738038172603642062
683 14607345120464483316993
684 15288902365907311180220
685 16001764993743087331059
686 16747348595275294345245
687 17527131781427577349698
688 18342658945249723264260
689 19195543143010304223493
690 20087469100191560267364
691 21020196346385388953185
692 21995562485895909662585
693 23015486608439417169505
694 24081972847275986879697
695 25197114089590761560843
696 26363095847029983025008
697 27582200291675274319978
698 28856810465977451347208
699 30189414672440357037322
700 31582611052241236642569
701 33039112359130228319275
702 34561750938513663281964
703 36153483918664723465658
704 37817398624741549365398
705 39556718223210343205378
706 41374807608190730558940
707 43275179538032477314174
708 45261501034544697325462
709 47337600053960578349923
710 49507472443034723653009
711 51775289190197679990709
712 54145403986218534638800
713 56622361105215042091853
714 59210903621599977766914
715 61915981974797526602806
716 64742762898547021565507
717 67696638727708275090439
718 70783237100712457533344
719 74008431071746531025625
720 77378349652247665589694
721 80899388797070479416328
722 84578222856450346598778
723 88421816510509898160160
724 92437437209102205525037
725 96632668135240654049789
726 101015421716712496403345
727 105593953705757351535718
728 110376877853355085403919
729 115373181199774567640941
730 120592240010030558687792
731 126043836377820954253289
732 131738175528862185965413
733 137685903849278594758536
734 143898127672415268136170
735 150386432851989970231770
736 157162905157600860466361
737 164240151522956205177331
738 171631322185701015943661
739 179350133751863735408541
740 187410893226884023024978
741 195828523049124874340850
742 204618587171162169304221
743 213797318227876496886954
744 223381645840237811088735
745 233389226097190516100513
746 243838472268413545149344
747 254748586794028142987864
748 266139594608221131308913
749 278032377846826875587320
750 290448712000362613928067
751 303411303566860986529782
752 316943829270881475564229
753 331070976907702039298393
754 345818487884348291305589
755 361213201521504730818666
756 377283101193660291067815
757 394057362376992802250360
758 411566402688492038526451
759 429841933991736483132720
760 448917016659459014298581
761 468826116074714002483856
762 489605161467943145607967
763 511291607178675772260166
764 533924496446891258234077
765 557544527830270592756944
766 582194124360707918599525
767 607917505544414100657130
768 634760762327987370133909
769 662771935143550880441827
770 692001095165049573222958
771 722500428898289670533841
772 754324326247299612105933
773 787529472189852183506694
774 822174942216042467917650
775 858322301673852272633701
776 896035709187806044074160
777 935382024306640689607740
778 976430919559269281667225
779 1019254997087925430673294
780 1063929910051983327603198
781 1110534488985354335158955
782 1159150873316291719561355
783 1209864648247651391386703
784 1262764987222985981584313
785 1317944800192889849349480
786 1375500887924821611976707
787 1435534102588510841375568
788 1498149514879430180752389
789 1563456587931552031934182
790 1631569358302640602196116
791 1702606624303946836491096
792 1776692141979959390917050
793 1853954829032384288479461
794 1934528977018168858028538
795 2018554472139834722367753
796 2106177024983994723085927
797 2197548409552338250910429
798 2292826711969063319345524
799 2392176589237138263903152
800 2495769538457677878814186
801 2603784176915156852778307
802 2716406533475425558575292
803 2833830351732008234559144
804 2956257405382886511807567
805 3083897826308611549371148
806 3216970445871941490923551
807 3355703149948020198167830
808 3500333248246256639539064
809 3651107858474122357196007
810 3808284305948187341500546
811 3972130539247077765294525
812 4142925562559282299251099
813 4320959885368474979187570
814 4506535990180598832033986
815 4699968818987154868983160
816 4901586279224255190775481
817 5111729769977747769122375
818 5330754729253591247008069
819 5559031203124053321703977
820 5796944437633166764541539
821 6044895494337026883185559
822 6303301890431612574535822
823 6572598264413836055704414
824 6853237068303127518866974
825 7145689287444886923444809
826 7450445189003521567395199
827 7768015100247959759409958
828 8098930217824003533631664
829 8443743449204356837780139
830 8803030287604045845797354
831 9177389721646893701202163
832 9567445181171342630055621
833 9973845520563520771990266
834 10397266041114197540354935
835 10838409553897738084379433
836 11298007484786420146569804
837 11776821023217027446965539
838 12275642316448809303610836
839 12795295711057773284058879
840 13336639043541820439319520
841 13900564981919699691385883
842 14488002420344142724906939
843 15099917928760884316786549
844 15737317259791006744173555
845 16401246915028579402429787
846 17092795773100188271617773
847 17813096781851010736909707
848 18563328717186182767577460
849 19344718011118163135227694
850 20158540651744976288284096
851 21006124157910470672732685
852 21888849631482650787756392
853 22808153890217128745677129
854 23765531684369111908124420
855 24762538000253534220431464
856 25800790454161511835508585
857 26881971780083209901096193
858 28007832414908786493982385
859 29180193184827255671869705
860 30400948096878556675238735
861 31672067239669162252322694
862 32995599797511788873158327
863 34373677182312338238867818
864 35808516287793195530515560
865 37302422870712801543981090
866 38857795064024227987656089
867 40477127026995263688025380
868 42163012737613269844699835
869 43918149932687652449622482
870 45745344201382687785934641
871 47647513238013730140399061
872 49627691260280138915947138
873 51689033599220222242082543
874 53834821467535594010760188
875 56068466913057009861623891
876 58393517964509105254499560
877 60813663976869961650030761
878 63332741184031610747758459
879 65954738466621138984442042
880 68683803343278742065116437
881 71524248193858993766952108
882 74480556723486577728899011
883 77557390676585424605886121
884 80759596810495397257660806
885 84092214138497667995938840
886 87560481452597400368319467
887 91169845136640306979895980
888 94925967280901586135629161
889 98834734109536436309491070
890 102902264732880090186959766
891 107134920236860661688679723
892 111539313122426165922971849
893 116122317108189148180630983
894 120891077310172435398994273
895 125853020812870554171655967
896 131015867646566323186856346
897 136387642186204515420047356
898 141976684987897412215332127
899 147791665079533404939005018
900 153841592722783980545723372
901 160135832664237496009264086
902 166684117894267103243146442
903 173496563932712992559561061
904 180583683661396623895981207
905 187956402724000393660626516
906 195626075514846262186548119
907 203604501778669099364036492
908 211903943844547474143580911
909 220537144517767046837558556
910 229517345654530199360482715
911 238858307445092205733569378
912 248574328432119169223796274
913 258680266291788193122892000
914 269191559406446911330588063
915 280124249258437986402307420
916 291495003676078234757168202
917 303321140963638782796713873
918 315620654948650156067075731
919 328412240980786610504938424
920 341715322918161438977893496
921 355550081137874861839262610
922 369937481609340393828254474
923 384899306070011167027439619
924 400458183344926251599356388
925 416637621852685026226246203
926 433462043342378431492639058
927 450956817907293584212577415
928 469148300323259729073932972
929 488063867760898534905855639
930 507731958923233051010760813
931 528182114661620384858427971
932 549445020125314012588260937
933 571552548501597041287121458
934 594537806405928548833305728
935 618435180983314808591006588
936 643280388784789113694636879
937 669110526484798195065628012
938 695964123508148162716493650
939 723881196637232863034014346
940 752903306673318271620934805
941 783073617227894093868915392
942 814436955723363920927864186
943 847039876684763213176979391
944 880930727407678623961023986
945 916159716090154193561251115
946 952778982520093889994808618
947 990842671412490813314104283
948 1030407008494793768196348705
949 1071530379441767381821566975
950 1114273411765456683843459809
951 1158699059769154133974543597
952 1204872692678815338716326892
953 1252862186068916569665557371
954 1302738016704609473126293323
955 1354573360925854566836851313
956 1408444196704413361200197364
957 1464429409508705437293114868
958 1522610902117094498279321737
959 1583073708524616673803157743
960 1645906112094106603753437300
961 1711199768107472969452019865
962 1779049830879228828795086445
963 1849555085599550988701821397
964 1922818085080936536774186684
965 1998945291588093996346697328
966 2078047223937971424582062205
967 2160238610062823314898829833
968 2245638545236986906770058238
969 2334370656174500124716783773
970 2426563271213001214668877155
971 2522349596806308019505062735
972 2621867900556959461959770018
973 2725261701027492568403564157
974 2832679964578730081108133030
975 2944277309491416631291108690
976 3060214217637703366407978751
977 3180657253977658097940153335
978 3305779294166846288285920746
979 3435759760570364721062218230
980 3570784866990333624828484145
981 3711047872423897230001140381
982 3856749344181215117179935314
983 4008097430703730398058884857
984 4165308144436298053995567489
985 4328605655118375399453471816
986 4498222593873699212215180399
987 4674400368490367113472538329
988 4857389490298453232349860963
989 5047449913065719305772061301
990 5244851384348253767472287980
991 5449873809747308775852531322
992 5662807630541009363732811211
993 5883954215175125615437902305
994 6113626265115714850942824763
995 6352148235583115078947211935
996 6599856771706683389584873067
997 6857101160657588576087175932
998 7124243800338266378657941888
999 7401660685226392402745974277
1000 7689741909994010189877860653