5
1 0 0 0
2 0 0 1
3 0 0 2
4 0 0 3
5 0 0 4
5
1 0 0 0
2 1 1 0
3 3 2 0
4 2 1 0
5 3 0 0
10
21 71 76 4
97 32 5 69
70 33 19 35
3 79 81 8
31 91 17 67
52 31 48 75
48 90 14 4
41 73 2 21
83 74 41 69
26 32 30 24
3
1 0 0 0
2 500 500 500
3 1000 1000 1000
9
1 1 1 1
2 3 3 3
3 2 2 2
4 5 5 5
5 4 4 4
6 7 7 7
7 6 6 6
8 9 9 9
9 8 8 8
10
1 9 1 5
2 4 9 4
3 4 3 0
4 0 10 9
5 3 5 4
6 7 4 4
7 2 9 0
8 5 4 8
9 8 0 9
10 2 3 8
100
1 24 54 68
2 60 11 46
3 10 44 11
4 7 55 71
5 6 28 86
6 76 70 82
7 35 48 28
8 73 11 60
9 22 41 32
10 79 45 83
11 44 17 41
12 57 56 53
13 25 28 62
14 60 37 47
15 91 94 56
16 83 42 75
17 12 24 56
18 96 24 78
19 89 18 72
20 54 13 73
21 64 79 37
22 25 96 33
23 52 30 57
24 53 9 30
25 82 74 28
26 32 9 74
27 37 99 44
28 0 65 0
29 78 16 49
30 75 75 65
31 22 11 66
32 84 14 37
33 70 69 27
34 8 78 27
35 53 74 18
36 98 57 35
37 44 98 10
38 61 53 73
39 1 71 95
40 98 93 61
41 60 12 73
42 81 11 45
43 59 28 58
44 1 89 85
45 26 61 86
46 36 33 84
47 10 31 0
48 54 90 1
49 42 58 45
50 90 45 32
51 6 36 73
52 86 17 48
53 24 15 44
54 4 71 23
55 90 31 6
56 69 93 92
57 28 50 62
58 25 87 45
59 92 89 30
60 21 18 20
61 66 36 69
62 91 73 30
63 48 58 97
64 47 35 97
65 36 79 19
66 0 88 68
67 48 42 21
68 66 24 1
69 77 75 28
70 20 52 87
71 82 4 59
72 29 50 38
73 37 42 100
74 35 83 97
75 86 68 97
76 65 9 22
77 4 79 15
78 18 48 55
79 53 22 9
80 53 99 21
81 59 26 36
82 60 93 31
83 11 26 57
84 72 48 79
85 5 24 42
86 5 9 34
87 33 5 57
88 22 50 79
89 57 95 42
90 28 88 90
91 93 44 15
92 69 26 86
93 0 68 1
94 24 39 22
95 6 69 52
96 93 38 26
97 48 90 3
98 35 12 27
99 0 9 12
100 13 28 36
1000
1 797 719 480
2 50 981 164
3 491 959 467
4 940 829 851
5 404 334 935
6 960 900 66
7 9 126 601
8 193 394 286
9 353 746 806
10 366 620 93
11 352 887 807
12 596 709 44
13 154 560 386
14 545 348 23
15 475 982 507
16 426 786 41
17 701 664 796
18 305 667 584
19 285 941 863
20 446 101 54
21 523 363 930
22 0 879 288
23 489 402 186
24 536 64 205
25 733 411 768
26 500 458 945
27 447 430 371
28 281 639 952
29 401 756 483
30 722 842 174
31 994 913 54
32 342 596 211
33 571 370 342
34 811 265 783
35 707 648 749
36 968 363 695
37 639 992 856
38 561 858 323
39 577 207 629
40 477 935 42
41 310 125 149
42 181 739 712
43 553 158 223
44 75 820 864
45 858 145 25
46 987 307 213
47 944 762 714
48 830 483 273
49 893 852 677
50 119 460 670
51 118 717 68
52 148 271 9
53 378 309 538
54 885 955 293
55 504 60 713
56 628 262 741
57 97 327 226
58 803 627 874
59 330 813 985
60 583 37 641
61 285 417 41
62 970 696 750
63 89 452 59
64 129 818 839
65 668 569 11
66 809 863 386
67 194 837 591
68 144 959 826
69 604 696 930
70 832 427 890
71 790 632 774
72 954 245 428
73 557 92 368
74 471 147 323
75 190 876 46
76 102 987 421
77 617 737 126
78 606 42 153
79 919 745 152
80 25 344 391
81 294 803 93
82 858 881 674
83 802 130 795
84 994 900 934
85 290 198 984
86 259 552 753
87 106 116 570
88 150 896 788
89 485 503 917
90 380 60 748
91 170 954 439
92 6 143 992
93 837 125 313
94 515 334 929
95 511 612 418
96 215 60 657
97 432 32 78
98 20 596 253
99 870 526 735
100 995 793 460
101 397 904 533
102 392 499 844
103 162 611 158
104 13 914 433
105 882 29 58
106 187 739 997
107 811 143 714
108 114 645 163
109 851 831 950
110 373 389 88
111 421 616 514
112 690 89 984
113 890 312 405
114 199 642 201
115 267 135 925
116 82 430 246
117 747 315 159
118 198 202 822
119 573 484 770
120 820 565 285
121 826 900 703
122 388 42 462
123 29 412 812
124 67 158 150
125 364 705 573
126 285 732 531
127 545 280 212
128 105 559 710
129 489 640 668
130 826 72 319
131 680 626 204
132 199 575 221
133 897 729 72
134 768 243 419
135 739 759 684
136 699 557 948
137 354 477 353
138 689 190 453
139 996 972 944
140 706 761 940
141 757 579 786
142 166 465 416
143 3 468 270
144 156 470 546
145 946 336 497
146 229 241 514
147 479 597 622
148 674 838 776
149 15 604 987
150 681 717 815
151 717 481 104
152 8 908 80
153 331 635 984
154 386 639 569
155 4 651 461
156 439 813 671
157 957 637 128
158 110 148 536
159 9 754 305
160 959 580 946
161 743 420 432
162 14 677 172
163 603 952 304
164 594 546 139
165 761 943 990
166 391 113 9
167 96 99 33
168 710 827 774
169 326 130 914
170 739 957 73
171 355 276 736
172 628 833 6
173 316 792 957
174 769 669 693
175 749 800 674
176 414 270 480
177 7 983 792
178 437 955 533
179 428 280 332
180 183 626 755
181 149 662 422
182 592 189 201
183 878 835 148
184 744 589 927
185 491 983 685
186 343 698 274
187 222 40 28
188 951 372 512
189 486 59 316
190 726 120 75
191 253 733 342
192 594 424 217
193 382 563 557
194 779 577 61
195 648 224 619
196 173 475 652
197 433 972 753
198 600 845 161
199 342 59 672
200 403 405 617
201 431 843 933
202 508 278 894
203 532 882 371
204 787 890 27
205 290 936 816
206 872 679 630
207 273 517 763
208 107 302 92
209 904 520 238
210 721 842 831
211 142 862 781
212 181 834 824
213 979 744 452
214 724 996 607
215 930 674 255
216 711 304 481
217 80 374 265
218 632 848 444
219 840 857 436
220 587 629 41
221 603 767 505
222 778 470 439
223 157 327 748
224 483 419 285
225 876 412 759
226 720 723 890
227 857 72 15
228 84 666 600
229 135 897 866
230 641 451 579
231 113 476 846
232 791 2 87
233 581 623 134
234 575 172 606
235 199 517 412
236 247 492 70
237 221 130 748
238 71 455 95
239 723 930 350
240 539 413 596
241 743 369 320
242 383 741 640
243 676 921 976
244 395 28 26
245 116 761 92
246 774 790 814
247 275 539 564
248 248 783 310
249 153 396 715
250 33 499 598
251 46 282 885
252 488 912 30
253 742 207 95
254 813 298 74
255 133 50 730
256 758 927 818
257 972 469 285
258 844 844 214
259 300 28 644
260 634 952 233
261 871 459 859
262 663 230 121
263 580 588 581
264 541 365 706
265 973 635 776
266 921 440 557
267 63 817 703
268 227 731 612
269 434 155 167
270 870 241 112
271 775 756 34
272 665 479 111
273 917 110 49
274 135 274 848
275 118 947 206
276 709 310 816
277 958 280 393
278 346 510 759
279 851 372 992
280 355 785 886
281 44 791 556
282 734 842 912
283 62 404 860
284 954 75 657
285 116 488 520
286 289 987 582
287 125 824 274
288 202 340 386
289 702 390 916
290 565 451 253
291 82 533 932
292 284 699 206
293 424 53 298
294 726 760 806
295 443 43 687
296 980 267 895
297 81 200 642
298 936 663 754
299 858 323 367
300 103 229 533
301 33 445 523
302 677 560 864
303 638 119 194
304 100 407 665
305 95 478 972
306 92 843 998
307 587 330 41
308 161 308 50
309 677 525 433
310 952 376 538
311 122 526 235
312 684 100 585
313 372 458 840
314 325 849 218
315 140 219 127
316 436 509 506
317 724 371 239
318 568 198 722
319 607 974 152
320 258 81 470
321 379 989 962
322 701 839 877
323 338 934 590
324 651 802 581
325 361 731 780
326 792 899 805
327 936 896 753
328 88 514 987
329 665 795 51
330 415 204 857
331 352 485 812
332 408 140 120
333 905 89 293
334 807 216 684
335 51 551 991
336 115 138 189
337 232 363 162
338 776 630 290
339 233 372 334
340 949 185 994
341 232 374 323
342 7 886 402
343 88 755 777
344 543 551 691
345 34 452 150
346 807 273 8
347 563 628 733
348 546 132 570
349 340 276 749
350 917 881 408
351 584 233 914
352 26 607 456
353 597 235 262
354 477 79 614
355 232 482 612
356 510 688 824
357 30 199 929
358 730 787 447
359 820 605 148
360 503 945 217
361 762 54 855
362 562 209 181
363 344 655 723
364 828 151 70
365 718 836 986
366 481 294 66
367 288 987 363
368 637 642 522
369 561 814 229
370 115 601 580
371 237 279 215
372 424 634 317
373 360 365 207
374 836 821 757
375 277 222 879
376 899 992 395
377 209 987 603
378 583 652 425
379 644 438 4
380 50 397 243
381 524 277 572
382 511 259 712
383 593 742 891
384 259 402 635
385 229 254 191
386 526 29 649
387 963 337 268
388 792 318 810
389 561 823 403
390 318 847 218
391 391 35 27
392 518 428 731
393 694 768 431
394 984 602 703
395 663 94 69
396 208 478 483
397 920 87 142
398 828 161 661
399 149 768 34
400 247 921 409
401 598 33 310
402 446 501 381
403 813 161 99
404 96 880 97
405 582 689 257
406 666 243 166
407 750 498 581
408 373 305 793
409 359 427 844
410 465 299 270
411 729 362 552
412 871 284 332
413 615 105 267
414 432 841 861
415 702 45 195
416 369 984 204
417 433 328 654
418 886 324 821
419 757 564 116
420 582 180 818
421 861 622 893
422 238 781 759
423 475 462 322
424 83 864 577
425 59 881 693
426 694 90 49
427 170 971 102
428 551 868 863
429 743 903 335
430 881 466 272
431 969 644 509
432 185 5 500
433 139 383 75
434 507 858 863
435 203 38 682
436 629 677 818
437 196 194 680
438 635 497 350
439 97 557 710
440 243 407 888
441 225 300 49
442 672 312 3
443 195 21 264
444 86 308 45
445 734 149 421
446 666 414 238
447 511 95 723
448 422 902 269
449 644 895 84
450 999 382 629
451 875 135 991
452 124 296 534
453 623 272 117
454 77 573 867
455 429 562 749
456 805 182 711
457 744 495 83
458 114 162 509
459 760 356 351
460 11 599 124
461 196 998 167
462 581 138 863
463 612 770 71
464 346 963 354
465 263 378 725
466 447 979 848
467 684 835 939
468 844 312 366
469 286 386 709
470 783 207 183
471 443 781 870
472 445 246 588
473 831 284 931
474 826 572 736
475 450 941 315
476 933 513 999
477 783 451 653
478 105 50 383
479 150 250 148
480 142 734 841
481 582 549 449
482 716 402 224
483 607 928 6
484 819 219 52
485 318 107 831
486 333 489 496
487 142 419 801
488 946 348 995
489 909 871 577
490 71 85 21
491 353 230 629
492 904 483 587
493 73 744 273
494 774 389 549
495 475 708 788
496 282 887 434
497 328 692 993
498 819 955 819
499 561 381 127
500 717 606 40
501 714 424 613
502 57 278 699
503 440 957 447
504 568 800 710
505 480 216 726
506 958 736 240
507 933 553 155
508 801 475 213
509 445 712 612
510 552 99 993
511 281 275 930
512 909 93 834
513 246 41 247
514 294 364 417
515 275 725 565
516 218 32 871
517 201 116 813
518 404 75 757
519 32 525 758
520 425 354 196
521 0 421 679
522 799 913 186
523 906 478 28
524 697 862 975
525 950 170 318
526 212 709 607
527 485 424 505
528 201 905 109
529 976 153 139
530 582 656 913
531 172 414 787
532 384 905 542
533 123 127 690
534 314 900 83
535 274 279 609
536 859 77 974
537 759 90 206
538 502 246 943
539 113 196 521
540 238 301 119
541 185 287 981
542 710 195 919
543 97 340 303
544 757 622 73
545 919 279 506
546 397 29 674
547 234 217 343
548 36 350 894
549 307 944 881
550 599 160 916
551 52 778 676
552 816 225 992
553 746 719 426
554 936 475 258
555 403 892 925
556 16 607 420
557 178 961 0
558 555 872 465
559 101 293 852
560 966 173 657
561 125 747 963
562 103 734 924
563 887 578 737
564 133 91 978
565 942 968 271
566 313 538 684
567 663 350 305
568 221 119 7
569 534 55 676
570 304 325 925
571 495 116 425
572 949 629 551
573 250 189 471
574 191 251 169
575 324 21 289
576 380 992 287
577 160 326 786
578 92 942 114
579 867 1 303
580 141 320 433
581 452 892 878
582 131 853 394
583 684 479 395
584 351 19 961
585 151 489 387
586 527 384 147
587 864 169 975
588 645 123 460
589 898 455 47
590 367 932 712
591 313 95 239
592 97 884 258
593 982 614 786
594 154 623 301
595 103 421 79
596 411 576 863
597 374 75 716
598 721 945 999
599 852 173 266
600 213 999 345
601 954 416 967
602 611 977 926
603 610 465 166
604 792 630 749
605 665 88 827
606 515 462 911
607 215 302 688
608 126 910 111
609 815 401 179
610 856 423 518
611 589 580 686
612 556 619 207
613 232 918 681
614 120 543 772
615 939 340 538
616 918 823 590
617 505 618 662
618 25 36 422
619 336 915 114
620 521 346 40
621 23 651 218
622 121 224 89
623 643 16 858
624 772 255 3
625 28 51 468
626 914 537 151
627 255 400 196
628 821 303 118
629 409 236 418
630 110 148 686
631 622 163 3
632 52 818 428
633 448 635 444
634 78 985 341
635 21 297 322
636 786 3 360
637 240 307 824
638 105 304 462
639 559 574 81
640 0 110 87
641 7 879 309
642 570 581 318
643 849 362 15
644 461 455 338
645 27 636 199
646 593 903 785
647 364 477 505
648 59 754 274
649 379 142 879
650 289 606 304
651 899 638 563
652 738 742 510
653 256 201 305
654 194 368 498
655 142 649 679
656 823 540 886
657 31 515 397
658 967 472 238
659 805 877 753
660 118 746 70
661 817 892 800
662 962 464 559
663 283 139 809
664 609 712 600
665 727 328 4
666 767 917 223
667 326 579 751
668 101 983 439
669 563 829 268
670 294 536 302
671 672 630 833
672 663 362 664
673 144 293 329
674 522 301 607
675 124 663 96
676 193 569 357
677 998 317 371
678 481 885 322
679 33 411 480
680 977 964 311
681 624 261 202
682 582 49 675
683 664 757 820
684 547 308 625
685 75 416 129
686 870 259 991
687 395 992 458
688 739 20 807
689 36 614 492
690 303 206 978
691 245 119 692
692 221 911 453
693 147 141 317
694 659 483 587
695 677 326 757
696 412 846 116
697 783 272 75
698 144 119 279
699 150 178 594
700 68 331 445
701 6 290 998
702 317 195 63
703 405 673 85
704 431 463 194
705 913 330 926
706 405 250 130
707 924 704 13
708 247 231 201
709 82 887 168
710 624 723 434
711 556 70 428
712 524 634 908
713 372 325 323
714 576 105 69
715 775 594 666
716 356 574 550
717 744 259 544
718 338 78 781
719 517 449 729
720 665 11 575
721 372 114 204
722 321 296 447
723 102 303 240
724 199 334 405
725 731 739 456
726 495 81 895
727 175 355 703
728 646 417 134
729 889 395 616
730 85 722 873
731 152 874 271
732 172 342 243
733 722 985 881
734 318 602 537
735 138 310 766
736 278 242 941
737 280 837 312
738 321 879 291
739 789 612 133
740 269 245 210
741 6 928 590
742 765 933 322
743 69 791 93
744 215 977 176
745 36 843 468
746 346 294 680
747 402 379 164
748 727 600 853
749 302 354 433
750 697 286 236
751 152 834 808
752 402 859 903
753 647 940 516
754 824 82 377
755 932 507 908
756 280 85 473
757 683 96 733
758 668 415 766
759 684 265 283
760 149 655 720
761 599 786 115
762 869 634 24
763 20 344 488
764 52 844 107
765 642 862 818
766 346 358 668
767 784 558 580
768 834 563 67
769 498 813 239
770 776 416 148
771 292 422 106
772 66 945 135
773 272 680 671
774 557 311 348
775 243 313 4
776 219 236 134
777 313 479 391
778 376 915 355
779 754 246 657
780 379 978 509
781 575 978 713
782 947 624 881
783 481 362 793
784 409 938 410
785 752 167 941
786 20 686 154
787 321 721 480
788 848 762 607
789 897 279 697
790 280 921 638
791 636 499 916
792 421 818 845
793 749 687 596
794 180 546 411
795 476 181 227
796 509 190 714
797 482 528 740
798 358 345 558
799 785 836 17
800 383 315 649
801 95 414 986
802 682 874 419
803 35 73 860
804 601 194 131
805 164 37 476
806 556 936 27
807 279 785 470
808 360 687 707
809 178 55 379
810 556 49 599
811 63 239 771
812 190 830 901
813 168 65 331
814 998 115 394
815 210 659 562
816 801 657 623
817 858 33 523
818 528 8 823
819 891 836 29
820 440 495 166
821 47 12 928
822 344 317 105
823 1000 908 799
824 614 195 385
825 456 496 609
826 114 932 364
827 270 879 754
828 494 273 149
829 738 247 610
830 214 729 467
831 115 971 345
832 871 424 664
833 886 955 361
834 358 44 473
835 655 414 605
836 989 390 758
837 750 553 98
838 226 166 32
839 908 758 579
840 119 636 725
841 890 549 251
842 181 561 572
843 600 304 410
844 190 810 816
845 469 207 265
846 665 64 615
847 580 753 775
848 345 455 975
849 418 930 840
850 368 734 82
851 289 651 907
852 755 948 916
853 592 675 36
854 777 604 919
855 272 748 914
856 537 112 127
857 118 769 239
858 169 43 875
859 186 838 615
860 118 510 905
861 687 936 422
862 686 953 810
863 280 196 616
864 892 843 999
865 963 905 707
866 531 503 340
867 816 195 834
868 506 459 985
869 876 434 667
870 938 642 193
871 394 193 202
872 635 420 926
873 987 93 355
874 954 94 92
875 662 296 763
876 568 103 447
877 643 650 525
878 670 57 534
879 362 81 873
880 470 805 803
881 167 402 996
882 970 326 290
883 198 875 744
884 644 311 24
885 768 302 666
886 399 61 986
887 483 683 20
888 656 920 759
889 416 218 101
890 249 917 587
891 38 366 638
892 649 853 876
893 386 170 202
894 444 744 155
895 317 151 660
896 704 560 445
897 700 889 897
898 332 603 704
899 214 76 320
900 582 862 183
901 170 544 338
902 967 285 494
903 532 456 992
904 700 410 951
905 287 978 574
906 982 74 634
907 578 976 296
908 668 428 396
909 641 297 150
910 641 961 302
911 859 487 79
912 258 205 353
913 119 156 632
914 166 31 458
915 331 117 455
916 116 312 71
917 596 587 489
918 943 254 368
919 191 781 663
920 92 3 879
921 308 712 341
922 666 368 802
923 672 676 934
924 507 783 366
925 677 181 4
926 72 109 234
927 795 882 91
928 215 590 700
929 755 690 333
930 298 482 906
931 579 622 118
932 804 586 136
933 44 403 302
934 495 299 76
935 647 320 381
936 764 3 351
937 895 649 317
938 779 709 324
939 711 9 763
940 992 30 669
941 191 707 214
942 110 923 223
943 905 217 396
944 448 190 776
945 573 51 917
946 200 877 254
947 431 897 235
948 336 204 38
949 876 878 211
950 40 23 287
951 490 517 165
952 624 779 988
953 38 274 636
954 136 995 478
955 964 889 891
956 272 314 86
957 179 858 919
958 56 338 927
959 812 839 304
960 996 984 367
961 63 246 954
962 374 57 941
963 670 304 563
964 915 154 27
965 688 189 779
966 612 168 238
967 597 963 584
968 935 634 584
969 190 709 529
970 267 985 952
971 451 971 190
972 195 690 678
973 808 96 821
974 519 373 761
975 863 929 611
976 436 324 129
977 104 103 551
978 719 670 4
979 273 639 561
980 625 775 315
981 189 179 568
982 237 494 117
983 1 774 632
984 686 692 495
985 129 84 196
986 786 174 228
987 822 30 180
988 680 993 152
989 294 741 63
990 790 0 275
991 999 882 473
992 266 820 960
993 845 651 222
994 910 29 463
995 278 501 271
996 813 620 451
997 74 733 20
998 312 656 432
999 771 968 598
1000 974 764 8
0