0 1
1 0
2 1
3 1
4 1
5 2
6 3
7 3
8 4
9 6
10 7
11 9
12 13
13 15
14 19
15 25
16 31
17 38
18 48
19 59
20 74
21 90
22 111
23 136
24 166
25 201
26 246
27 297
28 357
29 431
30 522
31 621
32 745
33 892
34 1063
35 1263
36 1503
37 1780
38 2109
39 2491
40 2941
41 3463
42 4077
43 4783
44 5616
45 6576
46 7689
47 8981
48 10486
49 12207
50 14209
51 16516
52 19178
53 22231
54 25758
55 29798
56 34452
57 39770
58 45877
59 52863
60 60867
61 69985
62 80430
63 92327
64 105896
65 121341
66 138952
67 158938
68 181685
69 207497
70 236812
71 270019
72 307688
73 350302
74 398580
75 453123
76 514795
77 584428
78 663073
79 751698
80 851683
81 964284
82 1091108
83 1233753
84 1394265
85 1574596
86 1777263
87 2004717
88 2260035
89 2546317
90 2867321
91 3226828
92 3629558
93 4080188
94 4584383
95 5148040
96 5778135
97 6481792
98 7267616
99 8144465
100 9122740
101 10213322
102 11428965
103 12782982
104 14290950
105 15969119
106 17836383
107 19912785
108 22221252
109 24786005
110 27635098
111 30798142
112 34308896
113 38203432
114 42522800
115 47310696
116 52616787
117 58494065
118 65002509
119 72206447
120 80178204
121 88995366
122 98745431
123 109522123
124 121430495
125 134583814
126 149108632
127 165141067
128 182833329
129 202349353
130 223871674
131 247597348
132 273745349
133 302552068
134 334280067
135 369212649
136 407663791
137 449973224
138 496516356
139 547699012
140 603970025
141 665814660
142 733767977
143 808409293
144 890376812
145 980361218
146 1079122683
147 1187483898
148 1306349297
149 1436698546
150 1579606663
151 1736237782
152 1907869535
153 2095885026
154 2301799537
155 2527254797
156 2774047953
157 3044125061
158 3339615185
159 3662823804
160 4016270730
161 4402685086
162 4825046755
163 5286582548
164 5790814524
165 6341555324
166 6942962487
167 7599537922
168 8316186926
169 9098218822
170 9951416596
171 10882038657
172 11896896031
173 13003359519
174 14209445941
175 15523828809
176 16955937339
177 18515970229
178 20215008209
179 22065036095
180 24079066568
181 26271169457
182 28656616534
183 31251916254
184 34074975549
185 37145149230
186 40483422209
187 44112469442
188 48056864792
189 52343154490
190 57000094649
191 62058744272
192 67552730549
193 73518363596
194 79994943335
195 87024893437
196 94654107870
197 102932120119
198 111912494260
199 121653024784
200 132216185863
201 143669369076
202 156085393529
203 169542792536
204 184126389915
205 199927641737
206 217045297577
207 235585798741
208 255664030368
209 277403800407
210 300938690067
211 326412614717
212 353980800916
213 383810442090
214 416081807714
215 450989018962
216 488741308947
217 529563929835
218 573699593780
219 621409526674
220 672975111240
221 728699124828
222 788907601755
223 853951273793
224 924207705276
225 1000082960306
226 1082014029412
227 1170470778128
228 1265958708967
229 1369021216799
230 1480242742254
231 1600251380024
232 1729722473979
233 1869381643244
234 2020008865211
235 2182441975554
236 2357581336344
237 2546393863663
238 2749918338147
239 2969270070413
240 3205646943914
241 3460334782940
242 3734714245292
243 4030266999693
244 4348583574288
245 4691370472650
246 5060459095545
247 5457813925327
248 5885542699977
249 6345905795233
250 6841327799276
251 7374408306588
252 7947935076558
253 8564896402832
254 9228496103105
255 9942167689983
256 10709591415435
257 11534710516077
258 12421750584184
259 13375238164647
260 14400022797063
261 15501298268173
262 16684627667529
263 17955967711601
264 19321697195146
265 20788644774299
266 22364121323593
267 24055951645803
268 25872511212259
269 27822762376811
270 29916296088268
271 32163373190914
272 34574971799039
273 37162834361239
274 39939521436246
275 42918465346197
276 46114031162669
277 49541577808124
278 53217527283972
279 57159434191042
280 61386064221439
281 65917473296993
282 70775096551561
283 75981838309171
284 81562172966757
285 87542247254670
286 93949994559620
287 100815251133975
288 108169885564294
289 116047930751185
290 124485730591698
291 133522089749230
292 143198439708040
293 153559008775159
294 164651010015391
295 176524834037328
296 189234261691699
297 202836682624006
298 217393335888003
299 232969557653258
300 249635053276414
301 267464177919359
302 286536244213222
303 306935839960434
304 328753175865395
305 352084445233186
306 377032216848121
307 403705841941025
308 432221898059339
309 462704649357994
310 495286547848580
311 530108753879695
312 567321701999110
313 607085689236150
314 649571513828635
315 694961139827556
316 743448417797353
317 795239835546446
318 850555331021888
319 909629139901814
320 972710712395878
321 1040065669853017
322 1111976838307333
323 1188745327886810
324 1270691697650850
325 1358157173055567
326 1451504958492341
327 1551121609964553
328 1657418513586867
329 1770833432917331
330 1891832173819484
331 2020910327997166
332 2158595147443514
333 2305447508354055
334 2462064020748456
335 2629079240143627
336 2807168041229032
337 2997048107591069
338 3199482601873626
339 3415282967642114
340 3645311932181487
341 3890486658817127
342 4151782122717227
343 4430234656350255
344 4726945743919121
345 5043086007638004
346 5379899471301673
347 5738708041203122
348 6120916295578504
349 6528016519776173
350 6961594085175981
351 7423333105566185
352 7915022476377677
353 8438562227228456
354 8995970300589112
355 9589389684074739
356 10221096017438669
357 10893505597839184
358 11609183913877110
359 12370854628625872
360 13181409151168472
361 14043916713643798
362 14961635103930360
363 15938021966898721
364 16976746835799979
365 18081703803191187
366 19257025004624878
367 20507094821307023
368 21836564987925465
369 23250370507693319
370 24753746575425516
371 26352246407226391
372 28051760192021562
373 29858535060553087
374 31779196303678957
375 33820769731536574
376 35990705423470272
377 38296902757298437
378 40747736986344911
379 43352087250257748
380 46119366308740806
381 49059551880898983
382 52183219902300892
383 55501579580082440
384 59026510581548196
385 62770602235363379
386 66747195107154343
387 70970424826140383
388 75455268553565774
389 80217593969002428
390 85274211195135353
391 90642927537346858
392 96342605492195162
393 102393223901013145
394 108815942739462619
395 115633171420763137
396 122868641141695355
397 130547481152745930
398 138696299524053687
399 147343268291175525
400 156518213599378176
401 166252710736338826
402 176580184720803752
403 187536016344731210
404 199157654391297711
405 211484733934445653
406 224559201502152142
407 238425447020264485
408 253130443382438757
409 268723893577965835
410 285258386292924463
411 302789559931469941
412 321376276050114480
413 341080802172123971
414 361969005056045629
415 384110554409741288
416 407579138214778300
417 432452689678943447
418 458813627080709416
419 486749106555711722
420 516351289195028572
421 547717622544146717
422 580951137988978003
423 616160764159390408
424 653461657965526341
425 692975553447779112
426 734831130192333383
427 779164401551704717
428 826119124574354740
429 875847231946770835
430 928509288018218182
431 984274969286821523
432 1043323571596094289
433 1105844544507347551
434 1172038055293926940
435 1242115583117710947
436 1316300546050837107
437 1394828961613248452
438 1477950143721433048
439 1565927436845037019
440 1659038990524221572
441 1757578575182399850
442 1861856442669129815
443 1972200232626775973
444 2088955928420393630
445 2212488863904143785
446 2343184785099184888
447 2481450968254605921
448 2627717398735212770
449 2782438012432741927
450 2946092004542630516
451 3119185207657700756
452 3302251544460354519
453 3495854557243955885
454 3700589020027201742
455 3917082635809548481
456 4145997825254047254
457 4388033609700823573
458 4643927595373292786
459 4914458062072879391
460 5200446163856117700
461 5502758245430442574
462 5822308282448782920
463 6160060449933916131
464 6517031827767699245
465 6894295248019386625
466 7292982293877583052
467 7714286455571074699
468 8159466453944079952
469 8629849737751203982
470 9126836166330189089
471 9651901884468810903
472 10206603402212116359
473 10792581887263930039
474 11411567683915046176
475 12065385067086308764
476 12755957246722028930
477 13485311632149284511
478 14255585373070378530
479 15069031187950909867
480 15928023498029520504
481 16835064878983935521
482 17792792850195232813
483 18803987015047937938
484 19871576574088374177
485 20998648226037076792
486 22188454480531936827
487 23444422399327311100
488 24770162792080529065
489 26169479885353802560
490 27646381493439572806
491 29205089711749987577
492 30850052164079821298
493 32585953826821238914
494 34417729464409958000
495 36350576701655407755
496 38389969770489681849
497 40541673959638359012
498 42811760808307467404
499 45206624075541628611
500 47732996530253041724
501 50397967597044027562
502 53209001907109259879
503 56173958793175586555
504 59301112782447607051
505 62599175130751879169
506 66077316456990172304
507 69745190525751892440
508 73612959242831956352
509 77691318916648733326
510 81991527856473191169
511 86525435366137037781
512 91305512210892764856
513 96344882622331535366
514 101657357926447384714
515 107257471866633406943
516 113160517714805891115
517 119382587250024886961
518 125940611706702044231
519 132852404780093985580
520 140136707800919741504
521 147813237175982344373
522 155902734217296223535
523 164427017466705483513
524 173409037650185657960
525 182872935379916200655
526 192844101751127873510
527 203349241964030619445
528 214416442131839665674
529 226075239418649565225
530 238356695683534222469
531 251293474789377325108
532 264919923769639283959
533 279272158027798936417
534 294388150781082291780
535 310307826941054656709
536 327073161662858445256
537 344728283775252458728
538 363319584345323223347
539 382895830611537011634
540 403508285563165927072
541 425210833423391302570
542 448060111340581591518
543 472115647570964813619
544 497440006486171956423
545 524098940717339886358
546 552161550800939993697
547 581700452669262830333
548 612791953385430168321
549 645516235500121807677
550 679957550467870816173
551 716204421537704215386
552 754349856597524257249
553 794491571428247474367
554 836732223892562144563
555 881179659559507368881
556 927947169339492729021
557 977153759680525934965
558 1028924435954663603681
559 1083390499639784454779
560 1140689859985231410441
561 1200967360825939336588
562 1264375123298709219481
563 1331072905190477642638
564 1401228477743431269169
565 1475018020718294583798
566 1552626536618503388078
567 1634248284954848571826
568 1720087237538462249924
569 1810357555767462679000
570 1905284090988192413299
571 2005102908990249633374
572 2110061839818022033950
573 2220421054060671792057
574 2336453666914535779038
575 2458446371292386363981
576 2586700101395090884817
577 2721530728143251414656
578 2863269788017250239403
579 3012265246837986291678
580 3168882300181970656541
581 3333504212110476151829
582 3506533194065060300608
583 3688391325770430040462
584 3879521520170347120950
585 4080388534413890782051
586 4291480029107193423217
587 4513307678040858611983
588 4746408330815047759197
589 4991345230783373958025
590 5248709290963568094739
591 5519120430566616831434
592 5803228975039159223141
593 6101717122522903801561
594 6415300479895325900370
595 6744729671570928502744
596 7090792024521608154863
597 7454313332996438476774
598 7836159706720718874280
599 8237239506383573367950
600 8658505370544654054016
601 9100956338128646465104
602 9565640071020987506978
603 10053655181326050371524
604 10566153668219094703639
605 11104343469382020014735
606 11669491132410209480109
607 12262924611648793225365
608 12886036196343244865550
609 13540285576073889527300
610 14227203049902222008810
611 14948392885756840747243
612 15705536837079210267793
613 16500397823866435097828
614 17334823785777451687047
615 18210751715104885752110
616 19130211877983837420790
617 20095332232365682549645
618 21108343051896828563392
619 22171581765022589198824
620 23287498019294421450101
621 24458658981064784236062
622 25687754881461997293337
623 26977604819772090425607
624 28331162836116599618826
625 29751524265581614090915
626 31241932386773557450541
627 32805785378078457234491
628 34446643595784582121920
629 36168237188568187885026
630 37974474063793111683770
631 39869448221457511597159
632 41857448472645362434079
633 43942967559769774108991
634 46130711696998896948148
635 48425610549736324952542
636 50832827673217169748533
637 53357771430819161028443
638 56006106413969944267556
639 58783765386132477517313
640 61696961774732373164883
641 64752202735560569187628
642 67956302815674752506317
643 71316398241568222519050
644 74839961860981773853908
645 78534818767562403945625
646 82409162639306082544775
647 86471572822641113199523
648 90731032195878622433312
649 95196945846776067924450
650 99879160600977444226797
651 104787985439222672798049
652 109934212843396397944754
653 115329141112735223070044
654 120984597693862967271437
655 126912963569703916935233
656 133127198754861523232963
657 139640868946574231601975
658 146468173383100036885437
659 153623973963063018001447
660 161123825682253719618175
661 168984008446229337307381
662 177221560320254974405919
663 185854312280169568446676
664 194900924531211659624353
665 204380924464088353773158
666 214314746321299431792407
667 224723772649201828343158
668 235630377615328091122896
669 247057972273191318396496
670 259031051861162093768823
671 271575245224990030606921
672 284717366458246542626702
673 298485468858245591063403
674 312908901300083052986871
675 328018367135034899112881
676 343845985725049618932432
677 360425356729018434559245
678 377791627262446938388186
679 395981562056480228727804
680 415033616748655225418853
681 434988014442496663027585
682 455886825680016237796139
683 477774051976368887329894
684 500695713073427099734390
685 524699938074721179016198
686 549837060632310703648838
687 576159718362375588472303
688 603722956675093429958639
689 632584337211177058400537
690 662804051086939414331177
691 694445037157196351737993
692 727573105515585076430105
693 762257066460011683631145
694 798568865162046229767986
695 836583722287973033782811
696 876380280831215346315010
697 918040759425563082502805
698 961651112421624844824495
699 1007301197019526946691526
700 1055084947764936931792291
701 1105100558727060840574265
702 1157450673692467350307761
703 1212242584721219138965042
704 1269588439428239518348144
705 1329605457366616703593717
706 1392416155907342163467039
707 1458148586025000842468922
708 1526936578418181814214296
709 1598920000409754996973452
710 1674245024092986746491720
711 1753064406207316842230852
712 1835537780250153062464525
713 1921831961350489292512674
714 2012121264454532771698691
715 2106587836394714308531079
716 2205422002439832779313623
717 2308822627947160952624653
718 2416997495765879280242021
719 2530163700066329754687363
720 2648548057300460581418210
721 2772387535026183716101085
722 2901929699361776820291109
723 3037433181866228079176737
724 3179168166677570788441579
725 3327416898773643372770571
726 3482474214258821510395360
727 3644648093615503540998696
728 3814260238901446799622230
729 3991646675912373962166867
730 4177158382375053137552932
731 4371161943277725963002623
732 4574040234494293928825495
733 4786193135903976900219062
734 5008038275261751780785753
735 5240011804124122676060844
736 5482569207192758199314879
737 5736186146492047174537893
738 6001359341859356141114317
739 6278607489284920423867759
740 6568472218706168312326274
741 6871519092924447615258950
742 7188338649385546590455503
743 7519547486634014089751025
744 7865789397330713442531519
745 8227736549797557207206393
746 8606090720139295848539239
747 9001584577073138510474382
748 9414983021689935751527529
749 9847084584458485646237037
750 10298722881885072500807594
751 10770768135335683730636371
752 11264128754637112093878113
753 11779752989176615111541109
754 12318630649337446709105052
755 12881794901219844951331344
756 13470324137724304320580537
757 14085343929195765186621102
758 14728029056964977848791102
759 15399605633255427128426935
760 16101353311073050345035284
761 16834607587839288576842259
762 17600762206688987604063143
763 18401271659510074721231377
764 19237653795976025327600892
765 20111492542990642448616428
766 21024440739152932137738842
767 21978223089032545466219707
768 22974639242249833186576458
769 24015567002552591967798397
770 25102965672301708521642364
771 26238879537992544553942818
772 27425441502676920650925173
773 28664876871383158951408708
774 29959507295888987539937626
775 31311754885454148260731087
776 32724146490397776882171363
777 34199318165678687754443588
778 35740019821937487671865868
779 37349120071755248085780198
780 39029611279208634765657229
781 40784614821121794501931888
782 42617386568766803924576104
783 44531322599111483058807732
784 46529965145093331209177655
785 48617008794774099823552365
786 50796306949640200828501065
787 53071878552721001759072491
788 55447915097640933006360917
789 57928787930161800575303903
790 60519055854251419512406882
791 63223473055191488798436028
792 66046997352756062174610628
793 68994798798008052198314892
794 72072268627821443535996204
795 75285028591795421819145013
796 78638940666832005619762070
797 82140117175253170774619615
798 85794931322987578223760300
799 89610028175010985980203748
800 93592336085931171476306228
801 97749078604315713389871197
802 102087786870124541853123813
803 106616312525374545404975869
804 111342841158988412513881340
805 116275906307607765739357678
806 121424404035041739210673481
807 126797608113917538067796697
808 132405185834062070296946159
809 138257214463112041163764528
810 144364198385889576629298022
811 150737086950127484295212391
812 157387293047251171427610982
813 164326712458056309351693241
814 171567743994334070085154530
815 179123310468719639756755989
816 187006880526349376150697887
817 195232491373234980206501585
818 203814772437677299267552385
819 212768970002472389654175540
820 222110972847189555912895659
821 231857338941346604982011635
822 242025323230956381723711747
823 252632906562588853995190125
824 263698825790873173286930121
825 275242605117168901113918454
826 287284588709057418522434926
827 299845974652254517873018712
828 312948850288619809666187721
829 326616228996045264193164179
830 340872088468244653742616320
831 355741410554741429433057682
832 371250222723769762553558474
833 387425641213261672456012895
834 404295915937702044126434453
835 421890477221288334347727889
836 440239984430647348338464189
837 459376376583228758830448196
838 479332925010533504635269950
839 500144288158431484334625505
840 521846568610101731402317331
841 544477372420471513430553017
842 568075870854568646981637302
843 592682864625810927355018708
844 618340850734073720597620844
845 645094092007273599524051132
846 672988689454324125386076717
847 702072657541526425171680644
848 732396002508899957827069887
849 764010803847499340149461784
850 796971299063555626466620069
851 831333971860180926143482412
852 867157643872544735409061119
853 904503570097718955389805169
854 943435538165964309366554520
855 984019971605937816818475446
856 1026326037262314497393220129
857 1070425757030474342842664581
858 1116394124079390817126129008
859 1164309223740501000235068357
860 1214252359247330952909967365
861 1266308182517817475324746319
862 1320564830178808460548393456
863 1377114065039956023052630662
864 1436051423232347497912640883
865 1497476367235559522983569516
866 1561492445025586773495097029
867 1628207455585092257887090642
868 1697733621026876911199764640
869 1770187765591167468872465855
870 1845691501787509652779771691
871 1924371423962515403765105171
872 2006359309585694935146681166
873 2091792328556885233791094831
874 2180813260850623751235509793
875 2273570722824979191998449615
876 2370219402535109210726883394
877 2470920304404928272839601406
878 2575841003624018327152367942
879 2685155910651051774194879443
880 2799046546219813158593783707
881 2917701827259144906587060673
882 3041318364154108731391062397
883 3170100769792079905692528383
884 3304261980854695259741711926
885 3444023591834279044546526618
886 3589616202271906465562564654
887 3741279777733343585742231740
888 3899264025059071752841789130
889 4063828782445164518082800465
890 4235244424933297721783783448
891 4413792285910327391899430766
892 4599765095241043776055656243
893 4793467434681579738838094603
894 4995216211245912954017766938
895 5205341149223618129483991726
896 5424185301573910306573377707
897 5652105581448724775489347515
898 5889473314626533862978981590
899 6136674813668444424298029661
900 6394111974639301769807811231
901 6662202897268671161586919627
902 6941382529460146166590568841
903 7232103337092055334115974489
904 7534836000088794808501736230
905 7850070135779301509944561175
906 8178315050598110972070485364
907 8520100521224597934744568467
908 8875977606297910493671507522
909 9246519489888346855682620601
910 9632322357951045313600360772
911 10034006309034414030552002127
912 10452216300564300087954032237
913 10887623132075021878743754335
914 11340924466810673607543843410
915 11812845893174073556994638103
916 12304142027557004202355633468
917 12815597660143483138063626025
918 13348028945338372680773253027
919 13902284638536166161125282063
920 14479247381009973400705855754
921 15079835034768031693226407019
922 15705002069295215779722294341
923 16355741002169457067528413981
924 17033083895618465043645064918
925 17738103911160099458367123234
926 18471916924550960576521596125
927 19235683203351653809120086027
928 20030609149504569940489460344
929 20857949109410289811244916857
930 21719007254082735366840680508
931 22615139532060313452820166072
932 23547755697851436066919268155
933 24518321418797295603640778563
934 25528360463343568013522733738
935 26579456973825133453127037046
936 27673257826984927518482842140
937 28811475085568966809784792922
938 29995888544465459478859388607
939 31228348374985991879012474458
940 32510777871022152234829387656
941 33845176300950865184631768045
942 35233621869307291753117678051
943 36678274792394627612077119791
944 38181380492156684179416532190
945 39745272912800967525521605191
946 41372377964828308650380120652
947 43065217101299125791231181154
948 44826411031347400683259278997
949 46658683576140581008324233660
950 48564865672678225187721671521
951 50547899531023412182981778093
952 52610842950770154400428908599
953 54756873802766378758902386348
954 56989294682336950580444437176
955 59311537740483783073326976863
956 61727169699781840782169350070
957 64239897061939857231101048512
958 66853571514254455315411328260
959 69572195542455105051670075094
960 72399928257716662032278105693
961 75341091445905094831030393846
962 78400175847422193995048476575
963 81581847676325524579901208443
964 84890955387722484043323708849
965 88332536702770994863672605078
966 91911825900966028448546380839
967 95634261389749732497546575373
968 99505493561855440541346196205
969 103531392951181160136457849452
970 107718058698388382896096305091
971 112071827337836086833757219842
972 116599281917889827072194918652
973 121307261467090657990156333708
974 126202870819130620956436953162
975 131293490810059461722825586770
976 136586788861643543210194139069
977 142090729965311359416788942204
978 147813588081653183265263948633
979 153763957970993934153331131137
980 159950767471131000255359308997
981 166383290238921207612053559166
982 173071158973016191211918486977
983 180024379135681777093021485492
984 187253343192297561991664389281
985 194768845387816336587543544043
986 202582097080172414385268270426
987 210704742651361933772664253423
988 219148876017680019052050897503
989 227927057761387925947690989654
990 237052332906901338009197410860
991 246538249365437408045923541919
992 256398877072936497612638033992
993 266648827846983421476428910857
994 277303275989396070596769876537
995 288377979662125110088297287228
996 299889303065120927957405901297
997 311854239445871671442426350664
998 324290434971403142529689963641
999 337216213494656041732395893061
1000 350650602248322843665817837836