1000
1 2 2084951038
1 3 2050033787
2 4 651809570
1 5 1205203340
3 6 1027489820
1 7 444113817
3 8 576877006
8 9 1591689679
4 10 965523423
5 11 1781799805
4 12 503013437
7 13 557618137
5 14 1030435459
7 15 1553988638
7 16 2012448025
11 17 1977682464
8 18 1429636937
4 19 303986072
16 20 1449611567
4 21 155342302
2 22 2020733154
20 23 2084841171
23 24 1200271252
3 25 1416675208
12 26 1555050666
12 27 1400309596
9 28 1779853425
15 29 434957982
19 30 1593565047
2 31 664490359
16 32 393494893
13 33 1003366457
13 34 1122352789
2 35 382725302
31 36 430874952
26 37 1055543830
17 38 531340993
31 39 563697997
21 40 2039909520
4 41 921035076
33 42 989053435
40 43 1167356839
34 44 1019800098
44 45 2065099907
10 46 1424759252
38 47 970146226
39 48 1251213005
22 49 1435788776
17 50 1495264652
28 51 9649032
5 52 1455613595
25 53 1674859630
6 54 1839295512
32 55 1598546592
28 56 1467745512
8 57 111949769
34 58 308013653
37 59 653881510
12 60 1193594389
21 61 417116168
20 62 1004241699
48 63 1184297208
36 64 405655370
63 65 516595245
62 66 51538971
50 67 245410626
22 68 653264649
8 69 1967138213
39 70 434787203
27 71 896911186
21 72 1318251733
41 73 1079410479
20 74 260974585
22 75 372598351
29 76 736539923
12 77 1942731817
60 78 638219470
57 79 165040532
26 80 1418926505
52 81 401783876
1 82 1528195421
14 83 1168303627
68 84 1885795016
27 85 1763714270
45 86 1534563000
23 87 1926493153
63 88 2065285203
30 89 449239347
57 90 701802196
39 91 1602511636
20 92 155863439
47 93 270073289
93 94 30837070
68 95 2100212708
67 96 423279841
93 97 1208044595
19 98 2073901054
34 99 39665209
60 100 713183628
68 101 1266013078
34 102 284917242
74 103 101267452
24 104 2067237784
70 105 496345437
29 106 1060690256
7 107 1117678384
50 108 84009725
6 109 855209603
82 110 504618509
91 111 2003896479
2 112 182019288
66 113 1965063571
22 114 8227267
106 115 250201792
114 116 1181547019
16 117 1917632455
98 118 1627170239
73 119 1250176411
38 120 254605064
93 121 155150855
51 122 1521688590
9 123 733480342
63 124 729836692
79 125 6539287
95 126 1984243344
126 127 710883722
92 128 1925299007
3 129 746239448
121 130 653825940
64 131 1704122432
9 132 1994180108
127 133 1961627187
3 134 593912193
42 135 1352025949
120 136 505369965
90 137 508686879
6 138 1652801351
99 139 1712908284
111 140 1422800054
112 141 1814003159
109 142 2056255774
114 143 1603647786
56 144 476136101
5 145 776049500
50 146 1896868228
57 147 50074099
25 148 1932142484
47 149 244332026
82 150 878039549
53 151 1001215847
88 152 1504433154
76 153 331795685
86 154 309534622
56 155 375025412
142 156 207022729
34 157 27791738
6 158 536245785
52 159 2078428121
76 160 1577312082
70 161 979810513
21 162 556407306
85 163 2045310487
133 164 1255777033
113 165 1135387825
136 166 196265479
149 167 771403286
138 168 1297907492
134 169 1728478934
114 170 1969745866
154 171 668168926
72 172 86624201
64 173 1267219094
50 174 782058347
144 175 483125999
36 176 942654311
158 177 137144051
65 178 667356536
85 179 1166036978
72 180 1958678598
129 181 1090116007
99 182 2009170542
30 183 1741155878
173 184 10222418
141 185 1218693085
3 186 753930748
113 187 1062751347
32 188 1289813500
83 189 144171249
33 190 1518163647
162 191 1184253072
136 192 1681042097
188 193 824136618
148 194 892206735
191 195 2026612078
16 196 822624569
162 197 95874453
43 198 63888108
143 199 527491042
169 200 1278046436
128 201 1638391395
183 202 2039527180
22 203 598408371
69 204 1291130282
147 205 352038510
38 206 720161103
108 207 2063215541
160 208 1972658176
166 209 1101323579
164 210 663417610
169 211 1932780497
185 212 898413392
85 213 959956892
72 214 885927972
140 215 1421954486
135 216 1273438266
111 217 1048650893
76 218 531703585
197 219 1981490080
215 220 833442322
209 221 687637855
216 222 715248020
166 223 2123843238
84 224 636297336
48 225 2110623424
94 226 856861634
163 227 1531860470
92 228 1769944188
20 229 683612625
65 230 458581558
7 231 267771629
99 232 684025058
28 233 1089857224
104 234 1251481914
121 235 1055425408
174 236 753880338
214 237 1643399516
89 238 1089465818
233 239 1431588012
94 240 375668092
32 241 991031162
102 242 208958931
239 243 1503058343
207 244 1982673278
198 245 1239510574
119 246 880485830
153 247 1159627779
43 248 1028710313
214 249 988893528
154 250 1669832774
139 251 610170291
161 252 2134213814
129 253 1265021518
211 254 1023061556
80 255 1847957500
221 256 2046108338
53 257 1774920081
29 258 1231739146
243 259 1458144981
25 260 296252291
157 261 675616887
158 262 1486095271
79 263 1569908329
154 264 2100083875
123 265 821524768
64 266 272427436
120 267 1198213265
111 268 1834540100
26 269 2010397607
191 270 1607608511
198 271 554077477
182 272 758407941
80 273 919899765
7 274 776082305
152 275 282903012
60 276 1919910499
108 277 170853724
164 278 877264729
102 279 2000536335
277 280 765892461
150 281 922175421
1 282 220436739
164 283 1739549122
87 284 123899061
219 285 428239696
218 286 84411709
108 287 834153070
114 288 1049013379
132 289 1946026268
76 290 1610388089
37 291 1685742290
106 292 1577628826
130 293 1978302789
32 294 1314765379
293 295 901836337
276 296 1627864855
28 297 1442905626
153 298 653745649
213 299 284325986
65 300 359878335
260 301 581876200
250 302 1461535941
17 303 1282183489
197 304 928773323
167 305 1281394607
164 306 2087152645
41 307 805202935
44 308 147540206
128 309 1303966877
8 310 494501781
63 311 1345555502
133 312 1708213215
91 313 150154629
189 314 1064597733
124 315 776493804
306 316 1715629890
18 317 344999582
128 318 2097560827
12 319 1657696095
27 320 1874947490
152 321 682966563
278 322 454162708
322 323 1453704114
165 324 1666908853
153 325 1108954621
302 326 2023875521
181 327 2006069984
237 328 536295655
220 329 1309523328
209 330 501087065
21 331 1231585487
277 332 314724120
230 333 766928083
294 334 1463790650
244 335 1772768662
60 336 903163292
240 337 1875976986
182 338 1852031525
315 339 512860936
139 340 1274381125
315 341 1939154743
113 342 1304045049
138 343 1205706553
132 344 636740777
343 345 898727686
134 346 1884800121
98 347 228640325
4 348 970774593
156 349 398078818
115 350 1690096055
299 351 1228769095
158 352 812010167
139 353 2127562091
149 354 1701531825
239 355 355914838
71 356 449426347
170 357 1969618703
26 358 1662937089
215 359 1919318937
66 360 756166865
139 361 192822676
343 362 1238585328
356 363 1287834005
264 364 1379806932
343 365 402113890
98 366 1051854728
294 367 121907069
283 368 1151059301
204 369 1278186221
182 370 292214824
185 371 339139901
283 372 99368857
136 373 150702584
61 374 1458536914
24 375 2034716751
61 376 451569352
73 377 1401269666
339 378 1419769714
163 379 772424792
96 380 449422537
143 381 1748516226
229 382 1741363838
84 383 2062044233
24 384 163118986
57 385 1190883889
301 386 820656392
78 387 2082030089
97 388 622194177
209 389 411918329
213 390 1564122818
163 391 339363559
250 392 1069222719
246 393 831204993
382 394 1921756275
193 395 645151720
159 396 506583068
22 397 1681592983
256 398 986861873
306 399 1541693895
359 400 505579067
327 401 1155428958
272 402 1437922749
146 403 799042587
99 404 1854656154
126 405 1843502471
23 406 1953797640
6 407 1195918476
247 408 2073103247
246 409 1089862479
271 410 372310448
164 411 166423481
151 412 1776561809
274 413 958110097
214 414 1538353995
93 415 376707691
160 416 1656977358
157 417 437044948
382 418 1550086145
367 419 2397628
313 420 625239353
29 421 687832742
274 422 1039390173
37 423 37218770
415 424 965635654
263 425 212310328
291 426 305362776
144 427 1758179845
154 428 2046273529
359 429 148154087
148 430 792435821
16 431 585875855
240 432 1781397024
269 433 298283820
173 434 148358009
200 435 656269280
41 436 358100133
115 437 498218976
33 438 784586132
419 439 1361428585
149 440 70040771
434 441 915154457
425 442 285440572
248 443 1488497803
72 444 1845685838
11 445 661077484
295 446 689020335
402 447 1186257845
446 448 1308712086
321 449 551826713
70 450 366846361
329 451 704114699
121 452 738173469
135 453 163220949
381 454 57497876
65 455 1780403223
231 456 2022469376
297 457 1077369750
86 458 1212357390
411 459 1985494873
25 460 1462767541
169 461 904344176
27 462 1423362588
150 463 367878787
416 464 1101122765
112 465 1229836748
308 466 944273330
66 467 45653301
257 468 354698110
28 469 1146633879
404 470 1853913578
245 471 1882904012
431 472 556187248
360 473 1109776600
101 474 83093137
259 475 858847078
84 476 1520407880
10 477 774383202
132 478 979277864
285 479 874731039
243 480 706212613
132 481 911020017
395 482 1657097422
153 483 145901617
405 484 834242667
331 485 1217178762
286 486 722834839
447 487 1709928610
292 488 78924269
377 489 508402725
97 490 286810021
154 491 1109716815
449 492 1233691706
80 493 1154761480
79 494 326845696
195 495 902032911
271 496 115904775
432 497 1827851276
284 498 1542492107
52 499 1055981129
67 500 447847450
40 501 1310602494
457 502 1348771216
393 503 237460989
10 504 298172641
167 505 79103355
31 506 1054394565
340 507 486124096
107 508 867053818
151 509 410319769
358 510 1519004121
391 511 2101802064
264 512 2002331836
371 513 2028288175
239 514 86809464
488 515 1140887892
39 516 754072555
333 517 96233696
323 518 139105556
36 519 368263978
60 520 1154175077
496 521 357437484
23 522 1259152771
509 523 101960358
108 524 1018779246
500 525 2039505871
255 526 1920449236
19 527 975023181
279 528 1441028870
289 529 1170048049
227 530 1498711700
311 531 1321573769
27 532 65168309
446 533 1152576145
295 534 652395834
81 535 1512142849
210 536 1060070665
464 537 1578972669
314 538 1189260692
376 539 485362593
147 540 775436864
206 541 62590816
526 542 418226148
406 543 1657022152
453 544 1105942666
296 545 1120131431
424 546 2022536589
267 547 616147419
209 548 152882046
536 549 1631868203
70 550 1589042838
217 551 1276082163
285 552 953641434
480 553 1139543990
147 554 156534734
410 555 1818995844
183 556 2075453515
210 557 1733021665
490 558 2013120731
187 559 261531270
352 560 1877053158
245 561 2037325451
530 562 2145488321
461 563 914803589
36 564 1279958451
125 565 1082039633
522 566 823061936
398 567 1923623076
296 568 1889353940
59 569 2074353756
160 570 475617614
107 571 404663047
399 572 1556688211
44 573 409232481
499 574 138855881
482 575 1264983572
95 576 470024543
95 577 516156901
132 578 1356196772
233 579 397487541
350 580 1816243398
459 581 298935425
359 582 1558466256
174 583 433109833
357 584 1088181093
70 585 410770010
223 586 1294235355
224 587 393647021
232 588 1641962636
473 589 1219095928
261 590 1503431971
18 591 705360294
296 592 66098641
471 593 163524052
101 594 1396191451
409 595 53193983
412 596 593028052
103 597 687944567
584 598 1873882170
388 599 1006968297
281 600 853795590
231 601 1451968945
378 602 1431562797
378 603 401797545
205 604 2100917864
92 605 879247887
3 606 1751156471
311 607 1632735190
151 608 537289315
190 609 1085564938
236 610 365797059
564 611 165201934
49 612 1065914129
294 613 1050035439
251 614 427096306
44 615 2014842766
331 616 216900435
380 617 1293388538
269 618 1655473226
226 619 1811187469
604 620 616094531
586 621 1246876210
293 622 1650010886
344 623 183280882
322 624 1798640932
382 625 373465608
109 626 1391296991
36 627 1639679322
6 628 831591937
35 629 1104651105
404 630 703734663
472 631 465677018
288 632 2098998445
510 633 857851216
305 634 1158531329
406 635 1653382834
97 636 412213655
541 637 951354613
290 638 180459383
114 639 991876657
449 640 473741691
600 641 1484645067
82 642 434276651
498 643 1185334359
195 644 756365477
63 645 1476297326
258 646 1691354534
149 647 858612443
53 648 727062811
148 649 1796320960
386 650 1566981424
62 651 406712482
515 652 2116622563
75 653 1580448650
324 654 1611221746
620 655 1926035833
414 656 21586256
453 657 1638221986
82 658 459702152
540 659 339438280
199 660 2128884905
139 661 130477376
501 662 1410013964
611 663 684335144
523 664 396993899
598 665 1087877170
160 666 1260615693
369 667 2013870744
557 668 883185521
328 669 680524880
320 670 1709103615
656 671 1601639083
516 672 1838962772
374 673 1163927175
489 674 1284733749
260 675 1536526810
635 676 521727764
303 677 1184385155
668 678 706457004
343 679 251349059
13 680 155017340
191 681 438561172
40 682 1229738301
139 683 68428165
375 684 575285456
88 685 1855077353
300 686 1718143028
322 687 894283741
128 688 1848378530
483 689 41814242
567 690 55643094
592 691 246944071
37 692 266012931
248 693 974152843
626 694 1150236780
682 695 352590700
192 696 889017481
66 697 1826845028
140 698 358357253
536 699 1266812752
507 700 1535965942
216 701 1609868323
582 702 492390420
66 703 987039789
47 704 586124779
668 705 2083313473
264 706 219661603
75 707 330883340
370 708 1886613847
584 709 513244976
65 710 790040617
202 711 780719472
699 712 343813317
210 713 828454962
12 714 1180132848
162 715 1808575540
3 716 541010846
475 717 1798008580
638 718 1865746808
337 719 1657875635
714 720 856567331
612 721 1010640278
328 722 152996036
16 723 422741628
570 724 301795512
242 725 1543248793
526 726 139137688
326 727 116822957
288 728 1179752883
381 729 1963403849
191 730 1623061145
679 731 1083621562
599 732 1065089395
235 733 380763930
21 734 1182007273
346 735 383058367
453 736 945311200
714 737 1951787966
550 738 1298155541
284 739 1693006975
142 740 1262063842
417 741 1941242516
177 742 1184199372
381 743 202632948
54 744 588534011
243 745 284475025
484 746 1318516539
23 747 543576144
415 748 561497042
348 749 17006080
83 750 405621450
27 751 1456818281
251 752 602126957
571 753 1539396083
48 754 1540909459
333 755 1375088108
24 756 1255761277
508 757 1050567671
585 758 167018062
750 759 856627013
741 760 1156234321
404 761 2107797940
254 762 1129794148
505 763 1190294616
55 764 540237599
596 765 195389114
242 766 410593138
554 767 946759932
140 768 1635506099
61 769 286387463
729 770 1809211870
67 771 1669854690
506 772 663596076
445 773 1002528261
131 774 800354317
660 775 373223503
696 776 2021336607
181 777 1499902742
679 778 844914597
605 779 299160863
699 780 457120272
192 781 653635807
583 782 737673869
175 783 1748795017
725 784 829396712
179 785 750738076
635 786 1567346661
710 787 1643948586
411 788 974955093
506 789 1879758132
487 790 1684133748
521 791 2026022631
407 792 1093634352
631 793 220042403
119 794 2066446444
63 795 1002195225
30 796 558061261
770 797 268601850
644 798 1301057071
367 799 467210199
326 800 333827759
73 801 1627824042
398 802 1748427124
4 803 7514473
793 804 1639661772
498 805 548223848
72 806 50092272
566 807 1012141098
791 808 1941359092
146 809 364993063
715 810 2134307351
52 811 1410812594
188 812 1129987602
264 813 142875457
475 814 744613334
28 815 730596512
153 816 1319779651
645 817 122456962
728 818 75207354
208 819 1626116648
525 820 2024326876
486 821 1614441242
625 822 1297056673
552 823 1321438060
562 824 1030228748
207 825 720703974
618 826 1113207901
450 827 449192590
330 828 389264589
794 829 420110949
212 830 1715211512
430 831 1666753675
801 832 1286111878
649 833 967838432
117 834 290074005
788 835 1944690372
523 836 505569463
614 837 785626484
837 838 616396279
65 839 1869297560
381 840 247277833
815 841 1527556986
701 842 1155248037
149 843 342137180
785 844 1399834851
308 845 906398555
70 846 589162959
359 847 226426019
656 848 191630515
649 849 1638148108
395 850 1837907968
195 851 745222010
803 852 1969230555
217 853 1704760273
313 854 612863538
216 855 1740159035
306 856 1769216260
281 857 523872922
857 858 154771719
416 859 1132753793
95 860 303502303
240 861 1827295600
449 862 83793799
732 863 15290105
544 864 1259210288
91 865 599182565
155 866 1228969398
477 867 406601394
798 868 407883076
626 869 666009835
183 870 529685985
442 871 1583234232
103 872 1015138335
639 873 700989326
315 874 1091240300
679 875 67515664
787 876 1357251116
180 877 502252608
558 878 1372225873
293 879 2143411352
399 880 775398342
743 881 519430238
440 882 1014948590
720 883 381212742
252 884 951259210
870 885 395335751
613 886 907294789
130 887 2051071223
610 888 279262105
618 889 1461837998
777 890 1728504653
269 891 310886231
86 892 555314484
313 893 1717965151
44 894 1455758736
470 895 1972670796
698 896 1642152839
648 897 1179276512
503 898 992219240
634 899 809043056
336 900 246582552
605 901 113891648
40 902 932676859
574 903 2104081067
541 904 544016653
752 905 727320461
532 906 1997253859
827 907 1892561320
659 908 1957889037
175 909 277589363
843 910 1345804201
80 911 1306123260
236 912 832939565
68 913 1771708555
509 914 1166904477
725 915 1166155847
788 916 2141084591
350 917 1463548362
426 918 1459729034
658 919 2089441990
624 920 2100629154
666 921 1845331633
845 922 1394751743
716 923 794173719
677 924 718056311
214 925 1727437575
475 926 474929552
13 927 128954936
268 928 2010197440
677 929 1450543850
577 930 341334012
671 931 43970837
64 932 837909022
592 933 1584122126
853 934 236799931
102 935 1053397780
110 936 626520457
218 937 1274450456
366 938 1391468447
358 939 1675054231
338 940 1531794576
772 941 825596964
255 942 1140775946
885 943 1888184449
397 944 1256735186
229 945 266063542
712 946 1688687370
536 947 1425273170
682 948 1897316481
708 949 1740254469
509 950 456067691
885 951 365751766
687 952 1982296535
261 953 1558976810
7 954 750123848
159 955 1463600288
466 956 1205081652
27 957 324356665
417 958 1775612901
337 959 469390298
419 960 1268729849
155 961 479263083
303 962 1692376865
260 963 1100566823
420 964 166804598
948 965 23057980
10 966 1928485684
386 967 1745560521
387 968 1390360134
699 969 749449898
652 970 1938457048
150 971 1578244767
806 972 897765703
487 973 1088366106
287 974 1435018631
353 975 1099892518
6 976 1469336515
335 977 1702907006
656 978 1113805492
933 979 1403945099
569 980 337984414
395 981 1413969617
459 982 457795201
112 983 455012871
139 984 904867816
379 985 1643221949
611 986 413763303
933 987 298337932
262 988 153311972
441 989 1488604678
912 990 1193529715
388 991 1939020061
644 992 1908685017
877 993 266909943
958 994 1310476759
558 995 745587193
606 996 1574894475
247 997 1218045857
355 998 1325555759
833 999 48992267
420 1000 164278693