0 0
1 0
2 1
3 2
4 3
5 5
6 8
7 12
8 18
9 25
10 36
11 49
12 68
13 91
14 123
15 162
16 214
17 278
18 362
19 464
20 596
21 757
22 961
23 1209
24 1521
25 1897
26 2366
27 2931
28 3627
29 4463
30 5487
31 6711
32 8200
33 9976
34 12121
35 14672
36 17738
37 21371
38 25716
39 30852
40 36964
41 44168
42 52709
43 62746
44 74600
45 88497
46 104849
47 123971
48 146402
49 172564
50 203161
51 238769
52 280290
53 328502
54 384576
55 449541
56 524910
57 612054
58 712909
59 829287
60 963682
61 1118456
62 1296811
63 1501840
64 1737620
65 2008178
66 2318726
67 2674458
68 3082018
69 3548112
70 4081164
71 4689796
72 5384703
73 6176899
74 7079927
75 8107858
76 9277769
77 10607569
78 12118801
79 13834152
80 15780734
81 17987261
82 20487743
83 23318419
84 26521928
85 30143838
86 34237496
87 38860133
88 44078313
89 49963729
90 56599367
91 64074777
92 72493213
93 81966375
94 92622444
95 104600445
96 118059325
97 133171691
98 150134293
99 169161128
100 190495252
101 214401454
102 241179630
103 271156736
104 304702185
105 342219114
106 384161763
107 431026328
108 483370651
109 541804336
110 607011409
111 679739766
112 760826805
113 851188609
114 951849054
115 1063928392
116 1188676703
117 1327462067
118 1481808504
119 1653384290
120 1844045127
121 2055822311
122 2290972385
123 2551965503
124 2841541887
125 3162701261
126 3518767246
127 3913377685
128 4350558722
129 4834716674
130 5370722528
131 5963906650
132 6620155397
133 7345908788
134 8148271769
135 9035016016
136 10014707160
137 11096712747
138 12291348079
139 13609890965
140 15064749853
141 16669487416
142 18439013354
143 20389619957
144 22539203582
145 24907313864
146 27515409340
147 30386923743
148 33547559774
149 37025377436
150 40851132228
151 45058388847
152 49683911922
153 54767810854
154 60353989797
155 66490331439
156 73229215833
157 80627749352
158 88748364663
159 97659104268
160 107434312530
161 118154986113
162 129909573021
163 142794400828
164 156914601229
165 172384631411
166 189329341759
167 207884609712
168 228198573661
169 250432397758
170 274761700276
171 301377473919
172 330487736646
173 362318637903
174 397116367571
175 435148478603
176 476706097013
177 522105500031
178 571690671464
179 625835182807
180 684945148865
181 749461461262
182 819863209907
183 896670330520
184 980447561165
185 1071807577749
186 1171415570123
187 1279992944460
188 1398322618753
189 1527253388549
190 1667706049675
191 1820678541788
192 1987253027730
193 2168601939512
194 2365996166426
195 2580812153396
196 2814541364208
197 3068798608844
198 3345332979772
199 3646037602866
200 3972962277793
201 4328324884143
202 4714525981704
203 5134162142773
204 5590042813517
205 6085205874163
206 6622937111864
207 7206788364332
208 7840599994845
209 8528522033322
210 9275040110880
211 10085000062170
212 10963637849020
213 11916608167124
214 12950018952914
215 14070464624092
216 15285065861046
217 16601508189996
218 18028087837376
219 19573756480415
220 21248174073433
221 23061760718840
222 25025757507171
223 27152286584779
224 29454421206766
225 31946255248454
226 34642983825870
227 37560983687173
228 40717905964135
229 44132769069231
230 47826065374183
231 51819868488871
232 56137955898894
233 60805932781857
234 65851372942395
235 71303961608801
236 77195657345404
237 83560856640143
238 90436579830641
239 97862660704119
240 105881959921312
241 114540583282726
242 123888126636556
243 133977927003372
244 144867343486212
245 156618046049419
246 169296337604338
247 182973485883090
248 197726092607664
249 213636474686170
250 230793087164349
251 249290960855314
252 269232186727090
253 290726418033626
254 313891424865668
255 338853669997865
256 365748943497308
257 394723022791995
258 425932398621964
259 459545031243769
260 495741180572346
261 534714272105521
262 576671845819815
263 621836547277471
264 670447211857211
265 722759998573382
266 779049628495208
267 839610681229606
268 904759008888154
269 974833217912756
270 1050196282873827
271 1131237239334058
272 1218373025052428
273 1312050413087687
274 1412748111630937
275 1520978970498441
276 1637292375038983
277 1762276763549110
278 1896562355458326
279 2040824022260717
280 2195784395467982
281 2362217139350715
282 2540950490237115
283 2732870985701724
284 2938927493639352
285 3160135459826048
286 3397581492835433
287 3652428200098767
288 3925919403478991
289 4219385643107529
290 4534250108278019
291 4872034898799334
292 5234367766861367
293 5622989237416758
294 6039760269213205
295 6486670348867636
296 6965846193366269
297 7479560947476676
298 8030244065785159
299 8620491759941064
300 9253078216230606
301 9930967457988942
302 10657326074869955
303 11435536687156860
304 12269212385434008
305 13162212007577122
306 14118656513103103
307 15142946310527474
308 16239779819397429
309 17414173116180196
310 18671480969133182
311 20017419105121721
312 21458088038845594
313 22999998301298103
314 24650097425707095
315 26415798521643725
316 28305010825737047
317 30326172054047328
318 32488282977207831
319 34800944038074927
320 37274394468847067
321 39919553722359562
322 42748065713524121
323 45772345681467063
324 49005630210642276
325 52462030218036695
326 56156587491187835
327 60105334581406142
328 64325358687536466
329 68834869333373931
330 73653270529075796
331 78801237219719107
332 84300796771767239
333 90175415302006190
334 96450089665662386
335 103151444911949865
336 110307838095572762
337 117949468258326847
338 126108493548255529
339 134819155298762163
340 144117910121416059
341 154043569846598244
342 164637450459855784
343 175943529883368121
344 188008615853920968
345 200882523765867923
346 214618265843805310
347 229272251537736162
348 244904500629307932
349 261578868971605732
350 279363288487395901
351 298330021383924645
352 318555930358588590
353 340122764796903279
354 363117464900653326
355 387632483799088944
356 413766129761178903
357 441622928622158466
358 471314008740078429
359 502957508667164032
360 536679010068423724
361 572611996155856592
362 610898338409518973
363 651688811950545873
364 695143642599801375
365 741433086100130068
366 790738042823944193
367 843250708574385379
368 899175265119392282
369 958728611216419802
370 1022141138116463634
371 1089657550477656505
372 1161537737061005465
373 1238057692336053195
374 1319510493792522616
375 1406207336310921144
376 1498478628854369952
377 1596675155092441992
378 1701169303732164533
379 1812356370460356693
380 1930655937838468731
381 2056513335386920450
382 2190401186823677963
383 2332821047072795536
384 2484305136694272148
385 2645418176779954354
386 2816759332724829441
387 2998964270403179274
388 3192707333994550981
389 3398703849538019588
390 3617712564380445098
391 3850538227216756223
392 4098034319904736789
393 4361105946450146082
394 4640712891466113254
395 4937872854289949325
396 5253664872297763286
397 5589232940485814151
398 5945789842224677094
399 6324621199250120039
400 6727089757303692939
401 7154639916606042402
402 7608802525238142750
403 8091199945869317878
404 8603551415743455583
405 9147678711769746457
406 9725512142656055434
407 10339096881510209426
408 10990599663083611736
409 11682315860850503554
410 12416676970567908085
411 13196258517487140637
412 14023788416589430419
413 14902155805230164196
414 15834420380574600510
415 16823822263683604126
416 17873792425958033620
417 18987963702562849183
418 20170182432211601342
419 21424520751018736062
420 22755289583853736838
421 24167052364348316001
422 25664639531468642820
423 27253163837643322273
424 28938036521303504465
425 30724984383108319645
426 32620067824170227382
427 34629699890324886412
428 36760666386789554913
429 39020147112567157493
430 41415738285597320202
431 43955476213928231584
432 46647862291259701605
433 49501889378714912499
434 52527069659308249962
435 55733464034288044979
436 59131713156783155080
437 62733070180075520901
438 66549435325819684534
439 70593392358581885123
440 74878247082943468977
441 79418067959594688903
442 84227728968722293983
443 89322954828285905399
444 94720368708795685514
445 100437542564586125111
446 106493050237892401300
447 112906523469484111922
448 119698710988380476990
449 126891540829672099546
450 134508186070869624020
451 142573134152740826842
452 151112259994809907831
453 160152903090257136834
454 169723948812189592382
455 179855914136838175253
456 190581038039699559607
457 201933376793245621937
458 213948904448755086826
459 226665618756441291304
460 240123652835704699790
461 254365392877986336337
462 269435602226339714702
463 285381552145532539028
464 302253159662414733328
465 320103132825045252714
466 338987123799597060136
467 358963890191915321042
468 380095465056064907112
469 402447336019204175568
470 426088634032889714410
471 451092332227109163078
472 477535455429812895578
473 505499300880172813076
474 535069670756395719886
475 566337117103726975128
476 599397199847473602628
477 634350758540125632572
478 671304198597945376316
479 710369792746210321727
480 751665998506214854616
481 795317792520661701783
482 841457022636213569058
483 890222778625364707249
484 941761782560787936268
485 996228799818763298472
486 1053787071828820597253
487 1114608771650464422220
488 1178875483608655345915
489 1246778708183985953850
490 1318520393515380973911
491 1394313494838243595937
492 1474382563354803915085
493 1558964365999683074613
494 1648308537750414106953
495 1742678268100449611847
496 1842351023512832763442
497 1947619307642467964278
498 2058791461330586575622
499 2176192504347225657249
500 2300165021089419068952
501 2431070092418022487273
502 2569288276065504307953
503 2715220638025886920740
504 2869289837606360308513
505 3031941268803276476920
506 3203644260954040735587
507 3384893341604705942773
508 3576209564844022476053
509 3778141908348981052227
510 3991268742721761527865
511 4216199376699270251110
512 4453575682177226689544
513 4704073803000099272530
514 4968405951857006868636
515 5247322299642353245867
516 5541612962059113152679
517 5852110088272029301823
518 6179690056869992615311
519 6525275784438417916102
520 6889839152530041166649
521 7274403558878017174005
522 7680046599221361685466
523 8107902886184045041009
524 8559167012217003124632
525 9035096663701484203777
526 9537015893925419780365
527 10066318562753894897792
528 10624471951477169089588
529 11213020561451912363590
530 11833590105866969063946
531 12487891704122841344845
532 13177726289087528317331
533 13904989237678087105410
534 14671675236053409787840
535 15479883390922806563126
536 16331822599379157265868
537 17229817189920707520839
538 18176312848303624601423
539 19173882842163261632870
540 20225234559400284730184
541 21333216375668910407052
542 22500824867449777694201
543 23731212387581524092358
544 25027695021364986144676
545 26393760941801720637204
546 27833079183871095573373
547 29349508858260565066227
548 30947108826417896182113
549 32630147859374035820119
550 34403115304360736191295
551 36270732283904260084198
552 38237963453783683766341
553 40310029346985295265273
554 42492419332635027121458
555 44790905219728921088427
556 47211555537487792845605
557 49760750525105694500606
558 52445197865837217027678
559 55271949201428779116841
560 58248417465258579733558
561 61382395073739042773184
562 64682073018095314459693
563 68156060899965233223684
564 71813407957043619756217
565 75663625126483290900433
566 79716708196779446054602
567 83983162100527727470848
568 88474026403718124704516
569 93200902049082717746058
570 98175979414567344824938
571 103412067750065091446249
572 108922626059406499609847
573 114721795496902864502679
574 120824433351927767130655
575 127246148697580963417002
576 134003339784028503809709
577 141113233259955554685538
578 148593925310510996483693
579 156464424803277653274537
580 164744698539172157378084
581 173455718708676793192714
582 182619512659641068091919
583 192259215086767007509023
584 202399122759233988936366
585 213064751907210623110626
586 224282898394894220105537
587 236081700812466707533131
588 248490706626848810607184
589 261540941536384329556311
590 275264982182732339863084
591 289697032379046084240174
592 304873003022374194401047
593 320830595864625697847917
594 337609391326070893161092
595 355250940542419854884149
596 373798861846993293902512
597 393298941897298444624690
598 413799241666712587984124
599 435350207530573564981584
600 458004787688364705467816
601 481818554173154206647939
602 506849830712923678127567
603 533159826718853155069901
604 560812777690287466075541
605 589876092337593429983633
606 620420506740062553070129
607 652520245868650982523406
608 686253192820695396088625
609 721701066127642728219696
610 758949605515704457860813
611 798088766514627401377511
612 839212924330306710516083
613 882421087413760811957076
614 927817121181329821410160
615 975509982359408488174149
616 1025613964451334618536291
617 1078248954844314791178480
618 1133540704100721207924293
619 1191621108000335749559868
620 1252628502928901020485506
621 1316707975232747098507125
622 1384011685190584301105764
623 1454699206280330257971653
624 1528937880452923252750805
625 1606903190154441445227173
626 1688779147874937426697567
627 1774758704034595295801610
628 1865044174058178940153312
629 1959847685524030327601385
630 2059391646317798397724670
631 2163909234759747516262947
632 2273644912722290674390533
633 2388854962796750637423070
634 2509808050620364518045810
635 2636785813520934463833235
636 2770083476693126821099090
637 2910010498171208437475401
638 3056891243924599887027529
639 3211065694458213560898052
640 3372890184366566435685910
641 3542738176351486288589487
642 3721001071286160202476249
643 3908089055974821933752202
644 4104431990336732333423886
645 4310480335815893785649205
646 4526706126904289317875934
647 4753603987746029553871367
648 4991692195883745902899681
649 5241513795295583486671884
650 5503637760973375129395957
651 5778660217387686626426168
652 6067205713296648888425679
653 6369928555459425966308545
654 6687514203936178544758017
655 7020680731769935507901675
656 7370180351977438185351092
657 7736801014900059339326743
658 8121368079109122688606018
659 8524746059195411780870904
660 8947840453928463041092492
661 9391599658419150021858754
662 9857016964088552391230385
663 10345132650407577592294811
664 10857036172556163071184105
665 11393868449327134258117151
666 11956824255800322483014698
667 12547154725504883507877971
668 13166169967005862949802120
669 13815241800060911381141480
670 14495806616730262706741653
671 15209368373052021657885850
672 15957501717152782037132640
673 16741855259913296163192301
674 17564154994589459435153525
675 18426207872061176605540817
676 19329905538686744765911583
677 20277228244037291469781110
678 21270248926117524462633332
679 22311137482002723253494377
680 23402165232182577441105190
681 24545709587255277527495357
682 25744258926007399459351074
683 27000417694299612493518175
684 28316911734604554080834730
685 29696593856462172326554529
686 31142449658581279406265029
687 32657603613772504533043276
688 34245325428401608107698124
689 35909036688549332004983933
690 37652317805611537896014285
691 39478915274614927928116351
692 41392749259118792585584073
693 43397921517162967718937094
694 45498723683368996577325149
695 47699645922943621445369177
696 50005385974036643121311414
697 52420858595604262108670586
698 54951205438692841892037840
699 57601805359819000603474662
700 60378285195951897252570872
701 63286531021431800085405146
702 66332699908060779479437038
703 69523232210502666109508227
704 72864864400109105490798069
705 76364642471269230873491727
706 80029935945444761012971001
707 83868452499119264855007895
708 87888253243046433379334912
709 92097768681342811588174451
710 96505815380226183552484284
711 101121613377463154419598592
712 105954804364953341299868583
713 111015470678250417146487714
714 116314155128301446678593485
715 121861881712178747513348831
716 127670177241187003105570122
717 133751093926351389398127136
718 140117232963039076367946654
719 146781769158230887487149025
720 153758476645856316991340042
721 161061755737522995397780086
722 168706660958030620336266543
723 176708930317143825049056361
724 185085015871333645715009968
725 193852115631462463828622862
726 203028206874813650368926407
727 212632080922328497040700318
728 222683379444546674565044012
729 233202632362420629771711653
730 244211297412032778638086060
731 255731801445149400641190285
732 267787583540647316178970130
733 280403140005004923582809366
734 293604071343415594540170512
735 307417131286508568168891373
736 321870277961315369490577711
737 336992727298841531616069991
738 352815008774566808020653853
739 369369023582238301214291799
740 386688105345620914339442138
741 404807083477257196982204155
742 423762349297953416133758514
743 443591925035471946036194523
744 464335535825970145644169300
745 486034684846896342287654773
746 508732731715541987691404160
747 532474974293060890452597748
748 557308734039719031448072437
749 583283445073228722416763828
750 610450747088476353048165674
751 638864582303561724357887828
752 668581296604067248716382223
753 699659745064645933385135740
754 732161402034607502987105151
755 766150475981961494872192581
756 801694029298605836175380153
757 838862103277788550524293115
758 877727848483892258863417320
759 918367660743744929461894369
760 960861322998332144467428330
761 1005292153263714095175898635
762 1051747158960434279205319749
763 1100317197881473349129365816
764 1151097146080164504952463904
765 1204186072971161474980403464
766 1259687423949864974804737730
767 1317709210848371700200290052
768 1378364210559355305704532772
769 1441770172173011988950297629
770 1508050032986664303051583322
771 1577332143761493121815382136
772 1649750503616536265771386233
773 1725445004966217045539843942
774 1804561688924641591028712766
775 1887253011617380095173331989
776 1973678121859837263919138151
777 2064003150680256475593573121
778 2158401513185323107415770220
779 2257054223286855136195881315
780 2360150221829646521047313789
781 2467886718682765217788658974
782 2580469549379977344876278461
783 2698113546919059856657067253
784 2821042929355072819713077809
785 2949491703848759911066832890
786 3083704087858652217623573120
787 3223934948193719115747200194
788 3370450258673085638714680376
789 3523527577169953379152227453
790 3683456542848992029653701191
791 3850539394439627339970629176
792 4025091510422435918189496746
793 4207441972041764578456694243
794 4397934150095347438202568988
795 4596926316490574100723239945
796 4804792281597822234145006950
797 5021922058473363126606090609
798 5248722555068465608686870880
799 5485618295586895860658014661
800 5733052172200756853955072776
801 5991486228383942861790918367
802 6261402475174154528366038625
803 6543303741727816572394898335
804 6837714561588152017057985676
805 7145182096144458090795822440
806 7466277096821125857143746856
807 7801594907597487661989651253
808 8151756509525029225766795656
809 8517409608976180553171916046
810 8899229771429708670253048790
811 9297921602670963052672018506
812 9714219979361821687732959509
813 10148891331014412332908775919
814 10602734975485535365387045341
815 11076584510194423923525191024
816 11571309261356087197731164021
817 12087815793615197095310660572
818 12627049482562390524928388701
819 13189996152715142811847957447
820 13777683783650168270839179177
821 14391184287082764677538394589
822 15031615357801840475316901187
823 15700142401486658468410946644
824 16397980542553856602864147339
825 17126396715310144263389161328
826 17886711841818541283396046963
827 18680303100023172336941837979
828 19508606285820835426192981581
829 20373118272915841404377480730
830 21275399574449422880537584241
831 22217077010555312016888475737
832 23199846486160409183631364106
833 24225475883522748859518721210
834 25295808074179811202322040010
835 26412764055167531295195899741
836 27578346214565796732919042815
837 28794641731628664289892987611
838 30063826116968723317752487829
839 31388166898483815187389097442
840 32770027458942526001651200983
841 34211871031381292696609844298
842 35716264858712532511016912725
843 37285884524198671405754424986
844 38923518459713335540004713695
845 40632072638986989434577443775
846 42414575463322082282816339415
847 44274182847560966712044384212
848 46214183514400714796899613973
849 48238004505471098978319947086
850 50349216917927774240640034877
851 52551541875660674557003117780
852 54848856744580281380015528239
853 57245201601820273858532782533
854 59744785969086712449953956180
855 62351995820789835177148764658
856 65071400878017471194295972878
857 67907762199847451214444386386
858 70866040083953067108382128394
859 73951402288929011141721335301
860 77169232591258300669543519941
861 80525139690351829940021153844
862 84024966475624529842266449146
863 87674799670123977990957850567
864 91480979865801987524162007379
865 95450111966115488296775693343
866 99589076052263368590219944824
867 103905038690009100072969854050
868 108405464694708570191390346217
869 113098129372856782086926430043
870 117991131259189785624269383417
871 123092905369127519067687553301
872 128412236987123199070918699208
873 133958276012293599939552344383
874 139740551883546248685772779202
875 145768989107292292394209058933
876 152053923411742024742495446924
877 158606118552721811877965892640
878 165436783796931120991864689170
879 172557592109574512716587740484
880 179980699074360741319947550808
881 187718762574957463534128059941
882 195784963268130675380297574062
883 204193025879980791864624165313
884 212957241357917716166744084635
885 222092489912293197275566294980
886 231614264982935994035972062743
887 241538698167211705697520592575
888 251882585147660643386569885603
889 262663412658751635513369550893
890 273899386533833552191223966759
891 285609460874967410950227278180
892 297813368389986895915928457924
893 310531651942861781000275542279
894 323785697365234159668493685167
895 337597767578859334589170649695
896 351991038080619153170360131443
897 366989633843783269752149105352
898 382618667691281115110189450083
899 398904280198912040527492868615
900 415873681188671442935948006596
901 433555192874704459825541308124
902 451978294726824761059953474673
903 471173670119051866462141282421
904 491173254833235469736893928709
905 512010287490547283666939933518
906 533719361986439626275694427706
907 556336482007593211039856283815
908 579899117712414604361642188788
909 604446264659794485112907700210
910 630018505074111963845371396254
911 656658071537865766536298390009
912 684408913206841433959387926584
913 713316764646382878168438484834
914 743429217391138676600295476871
915 774795794334596503747799883631
916 807468027058815772154466621210
917 841499536219017113129437624128
918 876946115102101152330469255250
919 913865816482746481100965927228
920 952319042905491920131779161955
921 992368640526139612313992553269
922 1034079996650938090317058736851
923 1077521141117316897137693028096
924 1122762851665462361131708172040
925 1169878763455746580787716232746
926 1218945482892965219016835550932
927 1270042705924503391556267343359
928 1323253340985950367611540577149
929 1378663636774322269942046102468
930 1436363315035946080513479673811
931 1496445708563207580994021870747
932 1559007904601790066457252570247
933 1624150893877729620519413246565
934 1691979725461607245423596848408
935 1762603667695488392422900286894
936 1836136375416828453525298721895
937 1912696063722489121695789211489
938 1992405688525278497226071437750
939 2075393134165038397333674420733
940 2161791408346280164479662660474
941 2251738844684716814322278042148
942 2345379313155780707317198381076
943 2442862438749354030488349094655
944 2544343828646501858575446119260
945 2649985308245986956474206507514
946 2759955166380791034128592847796
947 2874428410077772027650248235100
948 2993587029226982130584552154351
949 3117620271541060584597158992146
950 3246724928199531469821531257679
951 3381105630587784519349241761834
952 3520975158556031082291169901788
953 3666554760639613218014263699953
954 3818074486698738358380968437743
955 3975773533453021383570966900153
956 4139900603404179365059484373851
957 4310714277658848998687809213191
958 4488483403182824273348404934524
959 4673487495038050657220654854678
960 4866017154174505922214730617288
961 5066374501370656329955436682463
962 5274873627938546813767598127895
963 5491841063832775984167536501942
964 5717616263826670630876949976967
965 5952552112443922297291484819519
966 6197015448359832841535773159950
967 6451387609013150637396587918057
968 6716064996197319787100716635765
969 6991459663428827081974148308642
970 7277999925920274442005612831446
971 7576130994016845707825369662077
972 7886315630987038561074295051442
973 8209034836091914541271779567373
974 8544788553891749083219964751026
975 8894096410784860936565931156382
976 9257498479810636834610913968387
977 9635556074787366947571452383468
978 10028852574895544451733430005144
979 10437994280858785145439196527647
980 10863611303917570075385113904591
981 11306358488835635076955122631331
982 11766916372225110578594029392569
983 12245992177524485482815423795315
984 12744320848013220306790643264348
985 13262666119298402843765274604600
986 13801821632762319923785340059976
987 14362612091515250772172609189883
988 14945894460455272527166835704039
989 15552559212096449906145800651364
990 16183531619888566747022682332937
991 16839773100815594595106513747985
992 17522282609126497425118196670348
993 18232098083120793896857275938039
994 18970297946982661285093492344045
995 19738002669731325196540588341999
996 20536376383432166187635064889116
997 21366628562892450501088269078851
998 22230015769147995411918585511089
999 23127843459132477891755600474976
1000 24061467864009635342386060541389