0 1
1 0
2 0
3 0
4 0
5 1
6 0
7 0
8 0
9 0
10 1
11 1
12 1
13 1
14 1
15 2
16 2
17 3
18 3
19 4
20 5
21 6
22 7
23 9
24 10
25 13
26 15
27 18
28 21
29 26
30 30
31 36
32 42
33 50
34 58
35 70
36 80
37 95
38 110
39 129
40 150
41 176
42 202
43 236
44 272
45 317
46 364
47 423
48 484
49 560
50 643
51 740
52 847
53 975
54 1112
55 1277
56 1456
57 1666
58 1897
59 2168
60 2464
61 2809
62 3189
63 3627
64 4112
65 4673
66 5287
67 5995
68 6778
69 7671
70 8662
71 9791
72 11037
73 12457
74 14029
75 15810
76 17782
77 20015
78 22482
79 25270
80 28360
81 31833
82 35683
83 40010
84 44795
85 50170
86 56116
87 62772
88 70140
89 78381
90 87490
91 97663
92 108913
93 121450
94 135310
95 150747
96 167788
97 186747
98 207681
99 230927
100 256590
101 285063
102 316460
103 351267
104 389642
105 432126
106 478942
107 530731
108 587755
109 650783
110 720163
111 796752
112 881021
113 973988
114 1076194
115 1188867
116 1312686
117 1449049
118 1598833
119 1763681
120 1944634
121 2143641
122 2361994
123 2601933
124 2865067
125 3154041
126 3470741
127 3818316
128 4199076
129 4616643
130 5073858
131 5574971
132 6123343
133 6724013
134 7381029
135 8100231
136 8886516
137 9746746
138 10686708
139 11714490
140 12837034
141 14063714
142 15402863
143 16865489
144 18461404
145 20203568
146 22103641
147 24176691
148 26436632
149 28901097
150 31586457
151 34513394
152 37701300
153 41174235
154 44955167
155 49072241
156 53552398
157 58428600
158 63732618
159 69502772
160 75776551
161 82598670
162 90013036
163 98071906
164 106826849
165 116338613
166 126667761
167 137885099
168 150061417
169 163279262
170 177621531
171 193184071
172 210063954
173 228372711
174 248223514
175 269746176
176 293072821
177 318354051
178 345744116
179 375417933
180 407555019
181 442358532
182 480037537
183 520827466
184 564971707
185 612743290
186 664424845
187 720332964
188 780796048
189 846180450
190 916867597
191 993281608
192 1075864624
193 1165107583
194 1261523049
195 1365678403
196 1478167611
197 1599646520
198 1730802356
199 1872392983
200 2025213541
201 2190138611
202 2368087764
203 2560070368
204 2767148467
205 2990486589
206 3231311136
207 3490964157
208 3770861290
209 4072548970
210 4397659420
211 4747973942
212 5125374063
213 5531909738
214 5969748828
215 6441250021
216 6948908708
217 7495437732
218 8083708744
219 8716839303
220 9398132554
221 10131170246
222 10919748642
223 11767981239
224 12680229603
225 13661214454
226 14715944529
227 15849835809
228 17068636093
229 18378556441
230 19786190418
231 21298656206
232 22923514214
233 24668919662
234 26543535752
235 28556702024
236 30718341698
237 33039144201
238 35530471102
239 38204552583
240 41074389223
241 44153968329
242 47458160287
243 51002953279
244 54805349070
245 58883616430
246 63257183180
247 67946915573
248 72975005360
249 78365273312
250 84143057615
251 90335542063
252 96971642513
253 104082368367
254 111700705631
255 119862010712
256 128603897252
257 137966663317
258 147993178815
259 158729356169
260 170224037631
261 182529508411
262 195701392782
263 209799211807
264 224886284677
265 241030343718
266 258303440520
267 276782618229
268 296549833317
269 317692687940
270 340304364820
271 364484434912
272 390338805937
273 417980606444
274 447530161011
275 479115955945
276 512874639024
277 548952085621
278 587503425069
279 628694209783
280 672700485135
281 719710068751
282 769922663418
283 823551270192
284 880822348024
285 941977366385
286 1007273032520
287 1076982994677
288 1151398138884
289 1230828471576
290 1315603493674
291 1406074271961
292 1502613917289
293 1605619860659
294 1715514440578
295 1832747421470
296 1957796702127
297 2091171091416
298 2233411172676
299 2385092359213
300 2546825925911
301 2719262391694
302 2903092737545
303 3099052139276
304 3307921416556
305 3530531148843
306 3767763374343
307 4020556150456
308 4289905531846
309 4576870609168
310 4882575826012
311 5208216542045
312 5555061719682
313 5924460091085
314 6317843257290
315 6736732510076
316 7182742421854
317 7657588387240
318 8163090751762
319 8701183176608
320 9273917369732
321 9883472346225
322 10532159866653
323 11222434684365
324 11956900762178
325 12738322643773
326 13569632539807
327 14453942927620
328 15394554647170
329 16394970854972
330 17458906236251
331 18590302494140
332 19793338808486
333 21072449007520
334 22432333461268
335 23877978112611
336 25414667958271
337 27048008180046
338 28783939398501
339 30628761110663
340 32589148971428
341 34672180781112
342 36885356014257
343 39236624679218
344 41734409353609
345 44387637205212
346 47205764878095
347 50198814011862
348 53377399289927
349 56752767886886
350 60336831043671
351 64142207844665
352 68182260785877
353 72471144345466
354 77023844982187
355 81856235078697
356 86985117876630
357 92428287348467
358 98204578701694
359 104333934815265
360 110837462925804
361 117737508406029
362 125057718335639
363 132823123388966
364 141060209146710
365 149797006965759
366 159063173882706
367 168890093513946
368 179310965521059
369 190360917593440
370 202077105639351
371 214498838043858
372 227667687763263
373 241627630270160
374 256425168884689
375 272109487851797
376 288732592485512
377 306349479005662
378 325018291118386
379 344800508514692
380 365761121718131
381 387968841217634
382 411496292719389
383 436420249130765
384 462821848442535
385 490786851130175
386 520405883169052
387 551774721543361
388 584994565287981
389 620172352114978
390 657421060530991
391 696860061039286
392 738615452746279
393 782820452797275
394 829615771384948
395 879150043505600
396 931580246526410
397 987072178920185
398 1045800925036244
399 1107951385776847
400 1173718795861587
401 1243309311976137
402 1316940588186345
403 1394842427831302
404 1477257423388936
405 1564441678836760
406 1656665521106677
407 1754214300391160
408 1857389180862129
409 1966508027355557
410 2081906283892817
411 2203937955829787
412 2332976585802014
413 2469416341427532
414 2613673099063743
415 2766185648401148
416 2927416895568469
417 3097855196874370
418 3278015694212829
419 3468441791542747
420 3669706636628202
421 3882414755471588
422 4107203695950164
423 4344745836709866
424 4595750210105340
425 4860964503833704
426 5141177082093780
427 5437219200365346
428 5749967245735904
429 6080345187010427
430 6429327057576711
431 6797939665388650
432 7187265343816916
433 7598444948834744
434 8032680905999822
435 8491240524620054
436 8975459372190245
437 9486744938439904
438 10026580371393298
439 10596528527856091
440 11198236108855068
441 11833438136453398
442 12503962530498856
443 13211735055810203
444 13958784386024891
445 14747247570000521
446 15579375633315615
447 16457539617246409
448 17384236773961834
449 18362097236932696
450 19393890871091379
451 20482534639845700
452 21631100177783069
453 22842821925550977
454 24121105499899369
455 25469536674979306
456 26891890631556343
457 28392141871574611
458 29974474436735829
459 31643292851353337
460 33403233409984397
461 35259176253240202
462 37216257833596753
463 39279884239744753
464 41455744960759665
465 43749827585518513
466 46168432997899363
467 48718191590536801
468 51406080036337127
469 54239439170189310
470 57225992496699749
471 60373865908078623
472 63691608104416394
473 67188212332793375
474 70873138913226789
475 74756339202918503
476 78848280440295602
477 83159972157727117
478 87702993577670193
479 92489522719380806
480 97532366603516208
481 102844993323148313
482 108441565338610144
483 114336974808894739
484 120546880286888319
485 127087745636477664
486 133976880467929149
487 141232482998572760
488 148873684601588881
489 156920597002245840
490 165394361350594011
491 174317200183718917
492 183712471472008979
493 193604725820592109
494 204019765982909115
495 214984709819576892
496 226528055821851508
497 238679752396734572
498 251471269994620621
499 264935677345459315
500 279107720842782951
501 294023908415165016
502 309722596882859555
503 326244084215208194
504 343630705644243078
505 361926935132057365
506 381179491101711790
507 401437448016802591
508 422752352673885415
509 445178346883548901
510 468772295358173245
511 493593920579856873
512 519705943416920968
513 547174231366810669
514 576067953144501910
515 606459741602570873
516 638425863652308471
517 672046399288733294
518 707405428335621977
519 744591227138063846
520 783696473766087128
521 824818464086591346
522 868059337214479247
523 913526312839893212
524 961331938886278953
525 1011594352145449925
526 1064437550289384891
527 1119991678060677180
528 1178393325986758558
529 1239785844587445347
530 1304319672363023004
531 1372152680711591972
532 1443450534006899878
533 1518387068172775136
534 1597144685930481684
535 1679914772256790250
536 1766898128171239385
537 1858305426606077675
538 1954357688422433309
539 2055286782552307726
540 2161335948277121369
541 2272760343865693894
542 2389827619527356728
543 2512818519163383397
544 2642027508821684945
545 2777763436611485445
546 2920350221935664205
547 3070127579091814693
548 3227451773051305910
549 3392696412782480505
550 3566253279885070378
551 3748533198233750479
552 3939966942361153441
553 4141006190635302761
554 4352124520925524314
555 4573818455194246822
556 4806608550681162816
557 5051040544520796042
558 5307686549440448349
559 5577146307813962303
560 5860048501701643355
561 6157052126617325081
562 6468847926648395080
563 6796159899162101753
564 7139746866731065360
565 7500404125041301761
566 7878965164428937286
567 8276303474377304535
568 8693334428650433429
569 9131017260996905983
570 9590357129146379324
571 10072407277681166939
572 10578271297562212007
573 11109105493587663126
574 11666121357642958598
575 12250588159759381886
576 12863835654942301544
577 13507256918581660555
578 14182311308525197481
579 14890527567481236091
580 15633507063981211178
581 16412927186477320964
582 17230544888986332346
583 18088200403833651851
584 18987821120114860883
585 19931425644480427072
586 20921128043107635812
587 21959142282585793936
588 23047786868867765437
589 24189489703221107482
590 25386793154657440427
591 26642359369071138123
592 27958975814945691818
593 29339561087243651175
594 30787170969774834853
595 32305004779151416437
596 33896411991112220966
597 35564899173930555446
598 37314137230247217741
599 39147968973758835180
600 41070417042737979306
601 43085692178665215104
602 45198201872655219346
603 47412559409948274673
604 49733593315949340895
605 52166357236216621856
606 54716140254781851359
607 57388477685502178640
608 60189162341822321115
609 63124256322121421879
610 66200103317143634414
611 69423341479337915905
612 72800916861858158709
613 76340097469909228340
614 80048487933571933318
615 83934044847873921503
616 88005092790783299150
617 92270341068196916100
618 96738901198316713270
619 101420305188052571989
620 106324524615734832324
621 111461990576619061240
622 116843614507567014788
623 122480809951513482205
624 128385515280429495276
625 134570217441846513269
626 141047976750207867892
627 147832452792915803812
628 154937931475170254436
629 162379353278629654107
630 170172342761113802559
631 178333239377952237948
632 186879129655623788629
633 195827880804302440778
634 205198175803735910395
635 215009550055537301659
636 225282429640478416914
637 236038171280846859039
638 247299104051012795424
639 259088572943801022682
640 271430984340830413169
641 284351853502523900563
642 297877854131461063048
643 312036870133533213865
644 326858049636598025914
645 342371861400545097874
646 358610153685086109663
647 375606215719358984151
648 393394841846913611983
649 412012398501163245598
650 431496894092791841882
651 451888051976071155621
652 473227386584261914293
653 495558282913841785884
654 518926079457239236278
655 543378154777632855495
656 568964017835865351924
657 595735402277951349109
658 623746364804575991772
659 653053387847145770444
660 683715486684191077193
661 715794321240058428581
662 749354312713210956051
663 784462765294841398241
664 821189993139888515934
665 859609452871397919418
666 899797881796443134258
667 941835442136414855908
668 985805871467455805083
669 1031796639697467994561
670 1079899112794635319816
671 1130208723619365899083
672 1182825150095494169092
673 1237852501100178400605
674 1295399510331074970048
675 1355579738559964871341
676 1418511784556204240629
677 1484319505121263233098
678 1553132244544728455618
679 1625085073957709356747
680 1700319040923389506700
681 1778981429778123213723
682 1861226033094798483370
683 1947213434822294067052
684 2037111305507555344725
685 2131094710197803677426
686 2229346429467227459135
687 2332057294212865526259
688 2439426534705185130557
689 2551662144589007826751
690 2668981260365037229656
691 2791610557102690703183
692 2919786660963094032705
693 3053756579342412084040
694 3193778149267216892434
695 3340120504916265922119
696 3493064564957811603487
697 3652903540646186398325
698 3819943465429112946012
699 3994503747084426612333
700 4176917743205372607658
701 4367533361134073362423
702 4566713683235857150473
703 4774837618701464467511
704 4992300582849595476479
705 5219515205211253617561
706 5456912067454953999297
707 5704940472536211934756
708 5964069246224366428336
709 6234787572500312722829
710 6517605864080114886103
711 6813056669677067276976
712 7121695619367753848516
713 7444102409803147960064
714 7780881830750235144545
715 8132664834843993094069
716 8500109652165202676535
717 8883902951673837313338
718 9284761051254463741930
719 9703431178565254113905
720 10140692784599846612097
721 10597358912328486926707
722 11074277622493232998586
723 11572333479112479766430
724 12092449096949004422819
725 12635586753700644024187
726 13202750069362204325889
727 13794985755737889065434
728 14413385438763367134535
729 15059087556854539935343
730 15733279338170174633461
731 16437198860262149804567
732 17172137195247453375558
733 17939440644252879878882
734 18740513064533913591152
735 19576818293318062284447
736 20449882672063602717571
737 21361297675507100561494
738 22312722649504027117595
739 23305887662384709448378
740 24342596474169015978481
741 25424729628738674500948
742 26554247673677610418795
743 27733194513285747807491
744 28963700899873765176771
745 30247988069283162558617
746 31588371526168669163519
747 32987264985461153360560
748 34447184476012761478413
749 35970752613353788063757
750 37560703048065641759663
751 39219885097251375845123
752 40951268566151646100910
753 42757948767983320220178
754 44643151749636359486807
755 46610239731949068778723
756 48662716772832843541918
757 50804234662660344255316
758 53038599060875163711073
759 55369775883985677377522
760 57801897954643744288884
761 60339271922778815503586
762 62986385469290762951967
763 65747914804143747220862
764 68628732470231752314054
765 71633915465798723230766
766 74768753697721200233496
767 78038758779451107081516
768 81449673186939289127446
769 85007479787432243935496
770 88718411755556590273088
771 92588962892764772991558
772 96625898365738328396964
773 100836265881096111899832
774 105227407313280287684883
775 109806970804341654623433
776 114582923353875569876711
777 119563563919312241972024
778 124757537046301303064867
779 130173847050992894694692
780 135821872775562602099860
781 141711382940506431968227
782 147852552116788506101046
783 154255977343226813749575
784 160932695414073158039593
785 167894200864177283529038
786 175152464678713645551215
787 182719953757022437894130
788 190609651159725960713409
789 198835077171002653981115
790 207410311207535514190525
791 216350014608529892415352
792 225669454340859449988865
793 235384527656444199168076
794 245511787738662182584702
795 256068470377818990219409
796 267072521715435995115528
797 278542627100529210164661
798 290498241100832256545279
799 302959618715528255832422
800 315947847835887885876657
801 329484883004035332168877
802 343593580519953962430968
803 358297734950894461316986
804 373622117097303541535399
805 389592513473683155728259
806 406235767362818601867878
807 423579821506362239229768
808 441653762494869970655992
809 460487866925208632993381
810 480113649393454696592841
811 500563912396515932348259
812 521872798216011963608686
813 544075842863370127731497
814 567210032165510807824859
815 591313860076245850576995
816 616427389299057567126695
817 642592314313025659712035
818 669852026894352621991563
819 698251684232411490533440
820 727838279740077103688635
821 758660716664972891524382
822 790769884609272789934805
823 824218739072992414974083
824 859062384136898452720817
825 895358158408911573766058
826 933165724359279114063184
827 972547161178021327527753
828 1013567061289782734000437
829 1056292630669960754325435
830 1100793793107860040259250
831 1147143298571908992859377
832 1195416835834123703705544
833 1245693149520876014764690
834 1298054161759469914335330
835 1352585098600524278402155
836 1409374621398933941792205
837 1468514963347339096423957
838 1530102071359163934210127
839 1594235753510151694557581
840 1661019832250844383177270
841 1730562303615077516514183
842 1802975502653506674975273
843 1878376275334611763255901
844 1956886157160035199679446
845 2038631558755400292749716
846 2123743958702672244420344
847 2212360103895333421296103
848 2304622217703111032727670
849 2400678216249186304854035
850 2500681933108879711043904
851 2604793352756045546710834
852 2713178853090126420123158
853 2826011457395176023403905
854 2943471096089583732797907
855 3065744878644788016666323
856 3193027376059459935822978
857 3325520914296468020178932
858 3463435879098965610449435
859 3606991032624135619840324
860 3756413842343063547698779
861 3911940822678861047752193
862 4073817889866081155419064
863 4242300730539674585857965
864 4417655184573721451438241
865 4600157642717044839730150
866 4790095459585952351226501
867 4987767382603002379175942
868 5193483997485082566998113
869 5407568190914638855276825
870 5630355631043639291658396
871 5862195266512439114497762
872 6103449844682925449157562
873 6354496449820074314184275
874 6615727061974850905641392
875 6887549137358459798278552
876 7170386211018466452373681
877 7464678522666869071247303
878 7770883666532569792460061
879 8089477266152906224825547
880 8420953675043279721224830
881 8765826704228966338552422
882 9124630377649739407948218
883 9497919716496016736998271
884 9886271553564129122818151
885 10290285378769636810616877
886 10710584216989032116921347
887 11147815539454966981140552
888 11602652209964285621444079
889 12075793467216655192544369
890 12567965944638674228986732
891 13079924729110822639420456
892 13612454460054882374009859
893 14166370470406188877968355
894 14742519971038768313552230
895 15341783280282689818640299
896 15965075100220354708783743
897 16613345841524579787342688
898 17287582998652711871139913
899 17988812577292345212034507
900 18718100576009892482976244
901 19476554524140157263884497
902 20265325078015367239416373
903 21085607677724976816337854
904 21938644266662850767349051
905 22825725076217657358867026
906 23748190478032980589216730
907 24707432906369691027814315
908 25704898853179587620556043
909 26742090938612643350257835
910 27820570059762897651362430
911 28941957620579158943401677
912 30107937845956106804475431
913 31320260183150850247599704
914 32580741793766653176932040
915 33891270139683937173934596
916 35253805666423106369532886
917 36670384587571695080215363
918 38143121774021146285333444
919 39674213751916711970105348
920 41265941813345780668738042
921 42920675243959065533371928
922 44640874671850589673821873
923 46429095542203244736487668
924 48287991722348624102631004
925 50220319242083204220725294
926 52228940174236079042548737
927 54316826660690237761178743
928 56487065089224556522501195
929 58742860426764812621462892
930 61087540714810164386983593
931 63524561733038037664384584
932 66057511837282417185137796
933 68690116978333477474576584
934 71426245908213508679609436
935 74269915580854619518121755
936 77225296754326800645850556
937 80296719802054283514327965
938 83488680740698506381265819
939 86805847482695497822544915
940 90253066321694423732578617
941 93835368659475101106375942
942 97557977983201153778506554
943 101426317102219613883187922
944 105446015653918054443007758
945 109622917888529157926297926
946 113963090743095898803287380
947 118472832215215758211370536
948 123158680047530350142965045
949 128027420734360352340089181
950 133086098862260099692335723
951 138342026796729969066944432
952 143802794727727600137124892
953 149476281087115144235324719
954 155370663351613188260315860
955 161494429245362793848651191
956 167856388356663320660439314
957 174465684184021570519978187
958 181331806627149187843990396
959 188464604939152789282833514
960 195874301156700432862307716
961 203571504025598022483870472
962 211567223439788867627557497
963 219872885412485025153028414
964 228500347598762106966306430
965 237461915389693242553239936
966 246770358598767532158904997
967 256438928762134330515764708
968 266481377074934314898663654
969 276911972986829933020749384
970 287745523480621026894677463
971 298997393058742595786975760
972 310683524463272326197008436
973 322820460156050369995871554
974 335425364586406128370086445
975 348516047275029790086814950
976 362110986743484704606232902
977 376229355319972555189711780
978 390891044852992443686780384
979 406116693365728866439255875
980 421927712685108611786045955
981 438346317080743904448208733
982 455395552950165529536589178
983 473099329588116207177787716
984 491482451078948089771109540
985 510570649352630258420505394
986 530390618446239132060987046
987 550970050014368828894014568
988 572337670133365676996666627
989 594523277445964429167083344
990 617557782694478169452331435
991 641473249692484095035245085
992 666302937786636715413653472
993 692081345862155178354293474
994 718844257947343906318589485
995 746628790474554555257107581
996 775473441256941662379992993
997 805418140242556131382950248
998 836504302109406309665841004
999 868774880767461083470536783
1000 902274425835806303094680613