1000
1 2 2142937073
1 3 1079721420
3 4 955693063
4 5 2122585391
5 6 2013287170
2 7 661258139
4 8 1907454629
3 9 600567331
2 10 40260694
3 11 1339467221
5 12 1790942517
6 13 1985173252
7 14 1149691783
2 15 2111927008
13 16 1340270724
4 17 1858651722
1 18 66328820
5 19 817148543
18 20 1513396332
8 21 33860934
3 22 488283983
18 23 547568782
20 24 1885168179
1 25 565038609
2 26 366403925
2 27 2114688130
19 28 852989376
6 29 1343767893
14 30 238788467
16 31 1873700841
4 32 820963414
10 33 1272840282
13 34 497123274
19 35 614981946
29 36 360481284
16 37 1489245953
19 38 350879787
25 39 144375450
1 40 541645876
27 41 4066353
20 42 1646088837
6 43 1245213956
32 44 249011532
27 45 1451113957
23 46 2004746623
42 47 973681150
6 48 2066515114
39 49 801961218
6 50 126943704
23 51 2142579823
28 52 157198222
12 53 1812921755
40 54 1368539376
11 55 24759066
38 56 133017938
22 57 1766635183
14 58 573938987
27 59 1700667064
53 60 1264528984
49 61 102698819
1 62 1956180078
26 63 932549095
15 64 2072429913
24 65 880182592
46 66 1255409823
27 67 554433779
54 68 1248361619
9 69 171409440
10 70 1957518307
27 71 1034907223
67 72 1631905814
38 73 1172795433
8 74 506258167
21 75 1847263523
7 76 1697709635
20 77 2048642717
41 78 1403432820
18 79 773650356
33 80 481490105
40 81 1188329115
67 82 693987705
62 83 1508571310
14 84 413833897
11 85 1903073150
4 86 705145895
9 87 1295391256
58 88 807798414
78 89 1683605542
75 90 311802458
43 91 1177212526
83 92 1754395515
61 93 581684578
64 94 1014827847
30 95 1842373862
68 96 388793291
72 97 241480356
67 98 1298071339
9 99 1696981914
52 100 1285943067
55 101 6400683
64 102 1909019919
97 103 253689432
38 104 24572024
36 105 14913123
60 106 675429891
14 107 68000240
19 108 669650376
102 109 1886745351
65 110 723089782
19 111 1579925193
45 112 1208646365
64 113 1349682913
51 114 1673148460
27 115 2017980448
47 116 51412662
114 117 1015069281
91 118 1336608210
55 119 1001603641
53 120 637072346
27 121 453509814
68 122 77965563
54 123 1656216639
34 124 1666882248
40 125 323778924
116 126 441725911
100 127 603934721
36 128 680047042
25 129 921991226
125 130 952619589
126 131 1776833246
126 132 1255576259
38 133 1320090202
42 134 69633893
1 135 1853717116
118 136 728604954
28 137 960993177
85 138 1138622404
114 139 433053844
42 140 1611281680
122 141 1062491778
128 142 479088811
15 143 1489916432
34 144 657848971
115 145 1349056506
132 146 467155024
105 147 885238922
137 148 898035114
102 149 518351883
144 150 99771349
104 151 1482909587
62 152 730240265
34 153 1588034213
51 154 1691537032
2 155 1776350863
34 156 1323598094
68 157 1039313951
52 158 317359852
66 159 371576497
28 160 1608134307
20 161 367863000
72 162 1999325339
89 163 624560556
137 164 1114528694
47 165 1237578732
74 166 1158031960
138 167 133814092
107 168 89053125
22 169 524604526
5 170 725439040
73 171 1911585228
32 172 828466589
49 173 1156953425
135 174 1052428754
78 175 2096959539
15 176 1289852474
103 177 1957756549
134 178 263174603
144 179 488941186
118 180 237186540
69 181 561411757
115 182 2086850577
74 183 599198023
158 184 1512502482
26 185 771784505
118 186 88133899
160 187 1890124576
45 188 1088402084
160 189 112250637
1 190 438434268
153 191 222262543
140 192 1651236751
3 193 467040762
97 194 141232245
34 195 1549571927
112 196 1044051808
169 197 440681081
59 198 1102312395
8 199 409959537
112 200 1227797685
70 201 830153343
127 202 643681885
167 203 553285093
172 204 696601887
78 205 1919784206
66 206 256114914
80 207 213546971
128 208 885011966
205 209 555913898
167 210 1821272129
27 211 1430129907
167 212 594908297
124 213 618755942
190 214 2136611573
40 215 61547361
40 216 469396434
107 217 93221388
84 218 908891547
181 219 2057827051
9 220 157447695
113 221 1182377290
186 222 85094119
92 223 271420488
157 224 1027533753
94 225 1762475785
153 226 473891708
200 227 369723121
88 228 2074562911
110 229 1325579125
213 230 956810758
230 231 2077277422
174 232 771123207
169 233 1998388861
86 234 1531069669
108 235 255927150
143 236 708235375
104 237 1603745083
195 238 1920229237
76 239 20415742
179 240 1344109189
114 241 1419426836
134 242 1920294579
53 243 645471977
114 244 960025199
17 245 1602856974
232 246 993185286
136 247 1800756122
56 248 485671365
95 249 2046342957
147 250 368406078
30 251 1235236930
227 252 978699088
230 253 990464789
198 254 457631966
242 255 584345614
223 256 1174735985
11 257 1425110058
181 258 1836813640
101 259 2051376381
249 260 879937139
201 261 1547031857
130 262 1255878804
3 263 495911717
194 264 691730813
25 265 1956577208
90 266 620863776
106 267 22230573
212 268 1568909929
26 269 685840285
169 270 1334757228
65 271 1258823189
12 272 1009566254
109 273 911801292
195 274 623258663
217 275 672406761
146 276 317193880
203 277 1632266177
44 278 1703189048
157 279 709098129
135 280 1317063967
254 281 183962439
24 282 1368936533
124 283 650473999
49 284 774736768
170 285 1897311306
44 286 1082377071
174 287 913005478
35 288 1439080103
70 289 834784043
275 290 2142798932
208 291 2067616369
107 292 1800483578
41 293 1126852916
71 294 938834636
15 295 47288899
32 296 1570457094
197 297 2088365835
21 298 1298717790
132 299 1189464148
136 300 219412238
170 301 217453840
134 302 833197277
193 303 679612982
206 304 2123376639
146 305 997015432
10 306 461526993
292 307 644216353
23 308 960895908
180 309 972928523
245 310 1167190501
237 311 591865448
41 312 732524361
120 313 1284429951
244 314 151017018
1 315 1660808044
67 316 691864306
50 317 618697580
108 318 2027306675
47 319 1507754499
113 320 534798660
290 321 749551115
165 322 1338548885
123 323 1519734417
162 324 1087504501
5 325 1396984140
232 326 1599612383
298 327 887523668
115 328 1206698470
206 329 1573737812
22 330 1427743054
204 331 2053410242
206 332 1822559962
26 333 748958189
176 334 1544236941
156 335 1261794559
309 336 580079471
103 337 1703250919
99 338 282064056
29 339 1724063994
292 340 142762967
136 341 1537748433
299 342 1720053935
169 343 789949954
38 344 704574106
297 345 259089434
41 346 1163876079
272 347 1299033603
50 348 1619283971
159 349 1374905356
62 350 769264143
264 351 75499161
261 352 1637281568
311 353 1017099441
78 354 629191039
184 355 795063145
45 356 1655944167
264 357 888012039
101 358 945374801
280 359 1549376568
343 360 1087401021
136 361 1006845813
169 362 641752619
223 363 101868500
179 364 82522086
73 365 1003664538
289 366 133822972
350 367 2137964152
344 368 1774250499
3 369 872726807
44 370 1984513507
72 371 674949385
62 372 1803392879
362 373 1562684386
332 374 128941588
94 375 629798296
361 376 1131654198
17 377 974656450
218 378 328359107
96 379 1963703997
372 380 826818974
167 381 1164129141
71 382 1021876518
247 383 848408932
114 384 1857172123
278 385 66066004
85 386 616929398
42 387 107889286
222 388 2019302745
248 389 1480014522
138 390 51343382
92 391 1279745307
299 392 1033121410
181 393 1031856144
30 394 1938035992
89 395 895494346
108 396 1839610658
239 397 317148893
186 398 1080240092
330 399 491769563
208 400 1693905967
177 401 2060116278
147 402 1979964864
186 403 311472698
277 404 1598868069
86 405 665500313
72 406 535761171
37 407 585477082
333 408 871548242
122 409 2024005235
407 410 905340975
151 411 623666942
33 412 1028683360
54 413 590257427
123 414 1810931817
71 415 2058236247
50 416 446675571
30 417 162818230
290 418 947851821
417 419 1170666976
123 420 937029278
96 421 137372553
394 422 1793510190
108 423 1487940213
379 424 761146124
91 425 911076543
10 426 155098807
320 427 1602357156
72 428 457233659
125 429 1605598763
201 430 1916339526
399 431 859053026
24 432 1443078042
194 433 1559949421
231 434 548491872
364 435 960983022
97 436 1106062286
249 437 1223594747
362 438 197407017
168 439 860833046
90 440 1110377116
312 441 1050802923
174 442 1958613671
373 443 16712225
328 444 1603757842
215 445 1821379102
297 446 1894555708
431 447 2141910384
63 448 168480830
186 449 2091035409
288 450 21530364
127 451 1065482779
377 452 886355779
35 453 373600421
56 454 1178950071
181 455 1009974080
20 456 1236564791
318 457 1758798379
116 458 1383486972
418 459 1587768831
67 460 1444948388
199 461 322415182
202 462 334344138
147 463 1084616542
120 464 1285865621
153 465 377882039
5 466 1237955309
152 467 445214736
90 468 1920262750
466 469 1610054389
197 470 1441764829
183 471 156530956
181 472 1661307913
350 473 383302287
244 474 310155806
208 475 1785597614
269 476 897783694
260 477 100126195
160 478 1306736280
466 479 2022922092
75 480 266972700
474 481 1947830484
469 482 428687335
344 483 109480314
201 484 1608914177
17 485 1297841260
71 486 1029914761
327 487 2110201493
330 488 147898929
456 489 291114225
471 490 1208397718
171 491 908057021
221 492 761207930
118 493 348844267
145 494 1726054353
293 495 1322402415
95 496 1227178709
113 497 1099414602
258 498 1046812281
32 499 652510294
493 500 244080894
230 501 1663710663
482 502 1528503104
301 503 337218893
143 504 2091356227
447 505 831286743
256 506 995913489
152 507 1174174493
217 508 1815980832
364 509 1610688052
111 510 1366431712
289 511 1547680140
17 512 1699369458
267 513 801601156
330 514 2013350981
430 515 1937651142
76 516 1250562482
454 517 1896348465
395 518 1789579362
361 519 232989241
51 520 1127598421
276 521 1267120131
242 522 252339356
228 523 396724746
256 524 30307697
361 525 1037057006
245 526 1418205871
314 527 157933176
527 528 1113119102
425 529 314527110
213 530 93449163
514 531 1616162048
449 532 1790868437
248 533 2139045713
97 534 1967596043
3 535 196744899
100 536 345333562
208 537 410442185
30 538 104551028
472 539 1746377563
327 540 649164225
242 541 668635994
463 542 232443596
172 543 770532518
237 544 1129418795
310 545 1342696095
250 546 644092978
170 547 2049693981
106 548 519069400
250 549 483113204
85 550 1263370924
224 551 1620897437
304 552 489662721
517 553 1429211480
378 554 147830573
353 555 1999543817
542 556 990762981
545 557 1945171264
355 558 1843445381
218 559 1743417884
457 560 1165816202
190 561 1362491136
526 562 1222973115
125 563 1269904936
450 564 596691144
121 565 1831363671
210 566 1072052088
391 567 1787784498
18 568 103111739
475 569 751357353
204 570 1710333078
291 571 1571897896
507 572 1565655814
439 573 1024201650
300 574 655764998
329 575 128723350
268 576 1234453389
306 577 951279885
19 578 105376111
390 579 164263014
196 580 887555782
244 581 283601740
296 582 716360449
570 583 1998973903
474 584 1517383258
105 585 671638444
11 586 1165885078
172 587 1937269878
128 588 743524328
265 589 221005316
57 590 1929781931
458 591 1704151639
283 592 556856886
407 593 1496148408
139 594 1375879928
450 595 896143140
566 596 1426105732
224 597 1932344454
534 598 1033973429
159 599 688931872
62 600 1673574803
78 601 1423945685
518 602 909412419
230 603 1618710914
368 604 906929425
548 605 1308017568
44 606 1108901126
523 607 1970018837
459 608 1472168406
43 609 68473430
276 610 1619203968
375 611 1668994096
14 612 804880141
346 613 2033695867
555 614 885685117
94 615 1047850596
146 616 268313248
501 617 1305901550
82 618 1459702484
388 619 1452495951
166 620 1580268344
80 621 1517061386
86 622 932300331
402 623 928239163
376 624 341612694
96 625 145414426
369 626 361704509
146 627 645769244
551 628 1656996438
593 629 530068272
538 630 1759608003
580 631 330982392
70 632 1390474139
281 633 394913705
451 634 1419303961
122 635 1443385767
328 636 771151078
359 637 643190881
518 638 1141918131
16 639 1104105950
518 640 635488187
162 641 137467981
293 642 1191770813
54 643 1713309435
327 644 895356029
537 645 514833563
136 646 1275362813
165 647 1703063347
311 648 1418612363
245 649 1031154353
11 650 968611634
71 651 1893240835
107 652 537868239
514 653 1282827118
473 654 1265114526
146 655 971607677
343 656 1586985805
408 657 1135737470
48 658 67734584
533 659 95256849
401 660 807233145
461 661 1464904090
300 662 178576808
452 663 624246949
653 664 1842599005
327 665 1205753705
660 666 1416791098
235 667 948526411
88 668 1326008925
97 669 1116273057
67 670 1457361744
300 671 1656128416
6 672 983461186
535 673 32013810
479 674 776388894
406 675 1025775840
64 676 347382850
397 677 439549745
129 678 1407834611
377 679 221705151
127 680 456685761
253 681 1894420858
116 682 1352540176
382 683 2012885179
81 684 79222756
331 685 225640360
135 686 1544040446
7 687 132050418
20 688 1962250279
576 689 1260011505
536 690 959660388
639 691 879133539
139 692 1973786335
441 693 2000653679
372 694 1793586262
675 695 749659145
544 696 1282419488
596 697 116487025
134 698 1182395303
346 699 1264990485
284 700 480749490
120 701 1730110099
152 702 898772200
61 703 337497853
215 704 460936524
180 705 343962856
153 706 720114291
74 707 2074943112
433 708 2057940709
217 709 2076140335
292 710 2017301446
642 711 1872526124
247 712 1200482293
411 713 138717528
610 714 582860775
173 715 66174074
313 716 945379026
135 717 1555524284
297 718 1242887147
101 719 3707235
139 720 1724418838
654 721 1074736246
34 722 1700961097
190 723 456508282
117 724 148000262
502 725 1252146885
434 726 1536003933
507 727 1966957900
646 728 111420424
181 729 198815494
140 730 417678655
315 731 410839165
238 732 435362956
368 733 2111891701
608 734 1136557499
331 735 648759431
723 736 1538819903
184 737 1889859491
182 738 793982061
608 739 907582844
37 740 1678386244
107 741 334575090
480 742 810865005
113 743 1896580779
198 744 8971979
56 745 1407915205
159 746 128045057
504 747 794720751
706 748 2045444291
207 749 1196710488
190 750 914863611
521 751 1994614353
55 752 1813738108
456 753 1905004231
720 754 872179105
196 755 297371439
334 756 317397643
98 757 1543207835
634 758 1835766255
479 759 1275318828
418 760 1165048784
154 761 340872439
739 762 2101327260
90 763 318701393
380 764 289062972
649 765 1081916020
354 766 810489590
574 767 1486549470
37 768 1434549647
185 769 2011666619
93 770 1072033420
599 771 1462070228
285 772 1269757621
599 773 2041444985
571 774 1891935829
587 775 177954105
449 776 1201812715
476 777 146343470
510 778 1386190165
300 779 1203540283
284 780 846657616
708 781 1174219029
736 782 1813039898
376 783 1821959903
365 784 505921929
3 785 462486460
474 786 1758821197
383 787 2478981
711 788 606049385
616 789 1763946762
700 790 633304420
308 791 193361913
268 792 1839576785
740 793 759407524
734 794 149212357
536 795 1600731705
544 796 623822683
221 797 1938106628
251 798 805245209
322 799 1572898212
156 800 1685238131
365 801 1665080565
285 802 386379371
110 803 1483836669
699 804 1201269710
351 805 266967494
58 806 525406520
481 807 1201219881
326 808 1421479103
382 809 840004232
597 810 859266000
202 811 1947076547
207 812 797159910
787 813 2039328493
412 814 1420236741
776 815 1672456629
78 816 734813324
96 817 625497057
150 818 1355129159
647 819 492218004
398 820 1855706023
388 821 1225225827
502 822 36573197
38 823 779148819
394 824 253723302
783 825 638041963
465 826 409131896
733 827 1167748414
662 828 522354652
189 829 523440044
620 830 1651174442
713 831 544762088
693 832 1872039296
719 833 79961369
825 834 1344861182
211 835 679919194
365 836 816712666
375 837 614656691
106 838 1405056563
789 839 1848645844
379 840 1733176266
117 841 214335112
669 842 1218709584
369 843 758782709
615 844 489095285
494 845 377867309
672 846 516861683
117 847 2141982004
88 848 1165338620
228 849 752356177
282 850 935915221
546 851 1364070803
712 852 335108097
373 853 1759431502
285 854 1567888891
624 855 721560856
768 856 590145679
203 857 1280442852
358 858 1354422933
70 859 1729818138
292 860 1277687173
280 861 575233334
504 862 1695528672
552 863 2016663363
729 864 520969948
534 865 1311251103
169 866 243662982
837 867 1795507402
135 868 1031025088
868 869 606132705
381 870 1464365517
724 871 1468509888
146 872 1418088160
303 873 696365868
690 874 558814621
82 875 154919092
64 876 1959348522
204 877 493865333
838 878 1569720539
724 879 36347900
510 880 536617530
869 881 1569738821
536 882 1230100536
15 883 2125449051
685 884 131489215
334 885 839061237
63 886 894534109
381 887 685554515
542 888 1234433803
124 889 1248034901
108 890 1954607856
14 891 627966599
682 892 116959854
670 893 188329470
839 894 1474463808
417 895 1344058613
887 896 636212808
849 897 549937626
500 898 110711795
563 899 974164984
12 900 1561490174
47 901 2129804879
700 902 1163351965
196 903 85268378
239 904 1208370207
464 905 1853852398
593 906 1106139230
821 907 949769980
69 908 1012584404
768 909 600441507
477 910 527905778
513 911 1477290377
56 912 627673114
172 913 239164562
339 914 2095096209
609 915 1947531000
612 916 93803623
69 917 1605503
18 918 1922766576
762 919 1353089355
458 920 42904525
164 921 1041841994
337 922 1729031290
766 923 1902048537
709 924 1527767045
90 925 1166196872
133 926 1092640001
35 927 1981315775
655 928 281637684
483 929 1534427932
510 930 2085519519
102 931 1937778668
552 932 1105555372
790 933 1770593417
582 934 1933351792
113 935 988479576
224 936 1766742021
234 937 919696481
291 938 1860012778
32 939 1110910246
346 940 1003867851
936 941 1137820983
391 942 100012610
75 943 830767592
827 944 1066898711
80 945 71934416
490 946 237693198
393 947 1167822182
530 948 1007355265
493 949 735274218
6 950 832472061
589 951 289659442
335 952 299659956
353 953 495566766
462 954 287185298
67 955 2063242454
646 956 96512019
695 957 1175657760
601 958 1213105168
708 959 365825904
667 960 597605644
486 961 21174916
698 962 517481340
619 963 1862677248
122 964 63554720
226 965 1401789368
404 966 1277791685
28 967 1194857007
540 968 2022112043
771 969 715426761
920 970 1144488673
819 971 2102807795
338 972 452276281
409 973 1907138989
45 974 1802670043
790 975 1070894105
313 976 1017720068
797 977 770159041
955 978 1005082189
772 979 159501294
502 980 190169344
516 981 1710106626
562 982 1110497825
679 983 1887304762
510 984 1026034019
260 985 1322934272
369 986 1904183443
871 987 1208800622
439 988 736570326
905 989 690320361
429 990 1241579797
617 991 44654481
817 992 1964886104
197 993 2010667833
252 994 1024548238
375 995 1251760315
31 996 1941073988
731 997 846156870
456 998 691873551
32 999 104909857
212 1000 1654068742