1000
1 10 1234
2 3 98765
3 16 987654321
4 4 1225634
5 6 394
6 14 841
7 7 5395
8 6 1
9 16 33
10 12 75200432
11 12 5761
12 14 70031
13 3 17077818
14 10 12642
15 8 2071931
16 15 16
17 15 5461
18 14 5850718
19 3 116570
20 16 147791
21 13 26
22 8 6
23 15 2900
24 3 302811
25 3 3
26 5 1757503
27 16 29
28 15 8321769
29 5 1
30 8 9
31 13 23719419
32 13 1117
33 3 286406624
34 13 34
35 9 1063467623
36 14 6
37 12 1525800
38 8 306468063
39 5 6
40 5 1
41 3 707540
42 8 995006
43 4 2643
44 15 7692
45 11 12200
46 6 3583
47 8 48192
48 7 218797
49 9 3
50 9 1447420
51 4 219
52 16 361702
53 9 1515
54 11 3
55 8 876341
56 15 61098
57 9 2069115
58 8 3
59 11 110
60 15 4071217
61 9 3687994
62 8 5509
63 8 22689576
64 3 27
65 5 6524
66 10 5
67 6 2
68 5 1002
69 14 28971
70 10 487082
71 7 825164
72 9 460664019
73 15 61256169
74 4 75671109
75 6 4
76 5 35180
77 12 7596263
78 14 689802
79 15 570
80 15 28
81 14 3819
82 3 270725200
83 7 9
84 15 35223
85 8 120
86 10 11
87 10 227
88 6 518482
89 5 1457
90 16 900560
91 6 274567378
92 5 475519210
93 13 28
94 9 349085558
95 15 33341448
96 6 1182737
97 3 195
98 6 8
99 13 252684
100 7 44691
101 11 102
102 14 2076628
103 13 1314209
104 10 34112
105 8 34
106 3 179025717
107 15 2
108 10 14656
109 13 29
110 8 9982051
111 16 353
112 12 111102
113 16 207692
114 4 83756
115 15 387100
116 9 57
117 14 1913962682
118 14 3261487
119 11 14
120 12 4
121 15 1684624955
122 7 506452
123 9 87509058
124 15 430002
125 3 6050
126 10 36705
127 14 13556953
128 8 5916795
129 9 230
130 9 97
131 14 589
132 14 204409032
133 6 1
134 12 6282
135 13 13764604
136 9 4103378
137 5 32525
138 10 240519997
139 12 1
140 10 124380700
141 11 252177
142 14 590
143 7 464123
144 6 9504
145 4 196932
146 6 9868
147 16 55238
148 14 2633
149 13 119
150 13 4185760
151 15 966
152 3 13311217
153 10 19926
154 9 12
155 8 4425
156 7 730728
157 7 2239
158 13 510415
159 3 2109974185
160 4 29
161 15 4036
162 10 64393941
163 9 346692090
164 5 162566436
165 16 131478213
166 16 151852839
167 7 518502038
168 15 851015051
169 12 227930
170 13 559100
171 3 8667
172 14 2995
173 10 4845598
174 14 1520585529
175 9 36450970
176 6 3461918
177 7 19995
178 4 17535
179 4 23375
180 5 130369657
181 15 2565975
182 5 463
183 14 801272656
184 15 27
185 3 240838
186 6 7077185
187 12 1197
188 8 7
189 5 197752015
190 15 256
191 6 26
192 13 284343
193 3 112481619
194 10 38
195 7 577
196 15 2440
197 7 27
198 6 44266
199 13 1458
200 13 1451219
201 15 44
202 5 1280365786
203 15 7931332
204 6 174
205 9 553272
206 3 38
207 3 2027
208 4 119
209 7 3
210 16 31180
211 11 5886
212 4 252887
213 15 15
214 9 5
215 6 97832744
216 6 980768626
217 9 1021153
218 13 83742
219 16 109
220 3 146
221 5 30693397
222 15 313579
223 13 11264
224 8 49
225 7 88380825
226 7 1658832
227 15 1886
228 14 377
229 15 112855
230 10 441589
231 10 28965754
232 6 589
233 3 280063
234 7 818424646
235 9 90746
236 11 390096938
237 3 27837
238 9 312
239 15 2
240 16 22
241 8 1289781
242 15 181431685
243 3 14025
244 4 63
245 9 6438
246 9 18628
247 12 912154
248 4 1814
249 8 933
250 16 16547
251 6 1275145133
252 6 1843952563
253 13 1370641014
254 10 2030344
255 4 1052631
256 11 8553
257 12 1595352
258 13 802385259
259 7 218872862
260 6 2397899
261 16 977693
262 3 68533
263 3 300442
264 14 62
265 4 6
266 15 7299861
267 13 767
268 3 749525493
269 14 189
270 11 189115282
271 5 493851
272 16 64
273 3 227415250
274 15 4
275 10 292823658
276 15 30
277 10 238
278 5 30
279 14 2
280 6 3
281 6 7534
282 11 65371948
283 6 3
284 5 25
285 14 107574269
286 5 97291007
287 8 141
288 3 3911395
289 5 52
290 11 4842
291 4 884
292 10 6926
293 9 60199
294 7 5
295 11 1174216
296 8 23009
297 15 5
298 11 61721
299 16 190276130
300 16 9363
301 6 14185502
302 12 11916954
303 6 85277
304 14 63
305 15 3941
306 10 3
307 5 1903
308 3 3122321
309 13 551
310 5 2010472
311 14 752
312 13 291
313 9 4
314 4 180
315 3 4
316 10 62398
317 15 6195699
318 11 29824510
319 5 103653303
320 15 3098731
321 8 46395
322 9 457
323 3 36
324 16 3015
325 8 4722
326 9 486891
327 13 3084033
328 9 50565425
329 12 4740
330 3 905841
331 13 989
332 9 114
333 7 308
334 4 5545161
335 6 510884
336 9 185781
337 13 23007384
338 8 34429210
339 10 1161406
340 12 17525
341 10 16591609
342 7 16
343 6 364
344 6 47161
345 5 2
346 16 536781740
347 15 196
348 16 506037
349 3 10
350 11 2
351 4 11
352 9 39681154
353 12 911
354 3 1026137
355 7 3
356 12 1979545
357 10 3
358 7 35548
359 12 1256458434
360 10 7005491
361 10 56
362 10 83894
363 15 5493
364 8 1923084
365 9 184256165
366 15 128
367 8 22601201
368 11 1
369 6 4
370 16 27
371 8 232578496
372 3 31
373 5 56890
374 10 650
375 8 93997519
376 9 15988966
377 14 212131818
378 6 64802
379 5 548
380 9 8
381 10 284404
382 6 23
383 7 69254
384 13 1724
385 3 21160
386 13 86054551
387 4 2394784
388 8 344943919
389 11 162
390 9 3170746
391 13 1540
392 4 11414
393 5 12
394 6 2811201
395 5 640726
396 16 7836
397 11 15126602
398 11 1995283
399 9 4
400 13 487
401 6 15
402 10 14
403 14 2663275
404 16 4230476
405 11 12
406 10 502923
407 12 3
408 14 503758
409 5 13
410 12 63
411 4 178
412 11 154626447
413 12 3302
414 3 22
415 7 59236
416 11 114534393
417 12 80
418 10 14236
419 15 27
420 8 45851013
421 9 4076753
422 13 2
423 6 2161
424 15 435
425 13 132557
426 8 1304
427 11 525
428 9 5341
429 11 161
430 14 1344344
431 5 3
432 13 1384
433 5 430633516
434 9 666726285
435 5 253145
436 3 14
437 6 29805490
438 13 24289
439 10 7376
440 13 7448531
441 8 6
442 8 697529
443 16 366
444 4 6275
445 10 4
446 14 31
447 9 324418
448 16 472
449 11 3646
450 7 22062
451 4 7139030
452 13 886571
453 15 1235
454 7 432135301
455 9 2
456 6 7962833
457 7 3280558
458 11 74280
459 11 246798
460 14 3012437
461 4 297261
462 4 636462
463 5 94
464 16 286491783
465 12 615643
466 11 3277
467 3 649
468 3 445
469 14 30
470 15 1251646317
471 3 426478630
472 4 240373
473 6 212379420
474 12 725096836
475 15 11
476 13 26970
477 16 1862
478 9 6997665
479 13 4049821
480 16 1020537597
481 16 5
482 14 21389310
483 4 152
484 8 10754
485 6 16
486 8 4690
487 13 4
488 10 5129
489 5 1991725
490 8 208636
491 15 4
492 12 4
493 12 16
494 8 28
495 4 200914
496 6 118393432
497 15 16674109
498 4 15080732
499 14 7167928
500 3 367832219
501 12 481
502 11 89
503 16 167462733
504 16 31
505 11 584
506 8 34796024
507 3 481650024
508 9 68718035
509 8 29882
510 5 4
511 10 3966
512 13 30184300
513 9 112
514 7 3499253
515 16 50
516 9 31575157
517 6 4124508
518 9 122
519 8 377035
520 7 408792
521 6 86879228
522 15 107324
523 13 101
524 11 42
525 9 5
526 12 12890
527 4 233663676
528 9 318
529 11 57
530 3 342807509
531 12 60418
532 6 1102315331
533 13 207
534 8 1305256576
535 6 143569719
536 3 256135291
537 3 101619882
538 9 113643865
539 6 57
540 8 15
541 3 1012606342
542 16 26
543 11 23699
544 12 836
545 10 80385
546 6 5318339
547 7 2215
548 14 2828
549 3 7921
550 9 44840
551 5 168178
552 16 16499571
553 5 19969
554 7 8
555 16 1683
556 13 3826
557 7 1
558 15 8019
559 9 304
560 15 19763
561 13 358556
562 15 34224724
563 5 6627837
564 11 52346912
565 8 159560879
566 6 123
567 14 12196
568 4 2226
569 3 1453
570 14 440851
571 5 1557598
572 3 28547857
573 15 392718
574 6 263965
575 12 44588
576 12 16200907
577 3 21831642
578 6 7170
579 6 20
580 16 162968003
581 4 503
582 9 1
583 11 43
584 14 9248663
585 10 61191
586 4 767414
587 7 818160413
588 4 75493542
589 10 818227
590 13 116
591 8 15
592 7 46
593 16 4238474
594 8 7733
595 16 6385
596 12 1040493688
597 3 25726455
598 11 29
599 6 1
600 4 12082
601 4 1023
602 14 3298
603 8 891681854
604 9 4
605 7 4329
606 9 23479837
607 3 8
608 15 6917
609 12 842
610 13 5194534
611 11 185798
612 7 58162
613 8 2
614 9 6
615 15 3315
616 9 1992914
617 5 1461131467
618 7 248
619 14 238633
620 4 6244484
621 10 63227400
622 7 1646
623 16 6944369
624 5 77148
625 16 1925814444
626 3 52
627 3 1
628 9 16435
629 15 21139770
630 12 182
631 12 1197878
632 4 3004803
633 6 119533
634 10 115389
635 10 27111
636 15 179652431
637 3 29
638 8 275
639 11 2937718
640 10 1387
641 15 278256935
642 15 5471
643 6 31258866
644 15 100
645 7 27459322
646 8 4679
647 9 23
648 12 3
649 11 127
650 16 6660525
651 7 25278
652 11 3487
653 16 8303
654 4 21887
655 5 1767355
656 11 7708836
657 9 97435
658 9 414772
659 12 5896940
660 3 15539
661 3 342
662 15 175995861
663 11 61671
664 10 13182
665 4 365916
666 3 4417
667 12 394905145
668 6 10589125
669 8 24531571
670 6 63092
671 12 712381
672 8 53024744
673 8 3887863
674 4 320085950
675 13 7914
676 6 11236
677 14 100516
678 11 412
679 9 13
680 10 224521
681 13 8
682 12 7
683 16 31266
684 14 8970632
685 10 373795
686 9 231487257
687 5 392
688 15 412
689 6 1311
690 11 260118
691 6 4
692 13 165068784
693 8 39
694 4 20083
695 16 4560
696 7 566
697 10 6946707
698 10 2988370
699 9 62937831
700 14 90
701 16 1036659
702 15 116558
703 3 16846
704 8 1381
705 6 5854493
706 6 114
707 5 130618189
708 4 105781
709 9 137589022
710 9 41
711 9 29338397
712 8 10
713 3 3878
714 7 2882717
715 14 206
716 6 113
717 11 72834
718 11 113956
719 16 4
720 4 23
721 14 339180
722 11 445
723 3 28250078
724 5 20599601
725 3 794
726 16 8
727 14 495
728 11 406992822
729 3 1
730 10 26925860
731 16 440
732 8 234
733 11 3
734 3 12783934
735 10 82118
736 15 1815
737 3 11021457
738 4 262930083
739 14 11728578
740 3 28481064
741 13 8340
742 15 52629149
743 3 34449
744 11 369243
745 12 3641024
746 5 23
747 12 355177
748 16 570138
749 16 80
750 15 25029157
751 8 1953202
752 11 1
753 16 7566
754 13 3555631
755 9 2702
756 5 968795031
757 16 25
758 12 78876
759 9 455531
760 5 45079
761 15 225436
762 7 8467
763 4 30814581
764 14 49
765 16 36263
766 13 5638814
767 10 52421158
768 12 94713
769 3 1150528
770 8 4
771 4 1189154
772 10 700697
773 5 4274096
774 14 150318042
775 15 2232
776 7 192097351
777 8 201368
778 11 444348926
779 7 227
780 11 224472284
781 9 746605
782 13 7
783 8 7
784 8 399578704
785 7 98
786 7 165209535
787 4 10
788 9 14367129
789 4 35227
790 8 1630337944
791 4 23871
792 13 4
793 4 55
794 5 2373625
795 7 43509
796 8 32692
797 3 10
798 15 803533
799 5 8836
800 11 2086
801 11 32
802 9 304048
803 13 59
804 13 12
805 3 242031001
806 14 736
807 15 29
808 7 381305
809 8 5443
810 8 2620
811 13 2
812 8 2
813 8 17468
814 7 5474193
815 7 349500989
816 8 818423674
817 7 1534
818 5 12
819 14 459127456
820 4 3
821 7 49662270
822 6 418790694
823 15 65740
824 6 3910631
825 3 12255725
826 6 472343
827 15 6
828 11 4
829 6 36
830 6 109
831 3 5464
832 9 29452
833 12 2759
834 13 5
835 9 3832
836 7 331373713
837 15 68
838 3 5166630
839 9 4
840 8 69822654
841 16 14
842 9 374411008
843 11 316334653
844 10 194810723
845 12 1360
846 14 25424255
847 12 2
848 8 1734001500
849 15 184607
850 3 844568
851 9 124197
852 4 2879
853 6 414160
854 14 100735117
855 13 3
856 11 1947224496
857 7 344428
858 15 4745
859 11 5934
860 15 195712
861 10 72021437
862 11 4847
863 5 90
864 4 25251
865 10 37
866 9 4217
867 11 1903
868 9 20
869 11 454803730
870 14 126991
871 12 496470264
872 3 33
873 6 6
874 12 32244054
875 9 35077
876 16 15076
877 6 366999
878 12 507
879 6 18701
880 3 118900496
881 9 41315
882 14 6765489
883 13 16715
884 7 60642954
885 3 1703536
886 7 9290
887 12 17084998
888 3 187
889 10 50
890 16 221
891 16 346
892 14 199607010
893 15 491315593
894 9 22
895 11 29384
896 13 503309
897 4 4271
898 12 8124031
899 4 1
900 15 189582
901 16 116380160
902 16 934347535
903 5 498585721
904 12 9044090
905 3 822537798
906 15 29796856
907 8 8
908 8 1628298157
909 4 3490091
910 16 24350906
911 9 3
912 13 43
913 16 3
914 4 492
915 12 15838893
916 8 6
917 16 43701529
918 15 259025
919 13 2038
920 16 28648
921 12 16587186
922 4 71
923 9 7597
924 15 660271
925 16 489
926 14 6908
927 12 6141193
928 11 88902
929 14 201170
930 4 110
931 13 30102
932 16 3309640
933 13 516289
934 9 1
935 6 79353
936 12 6796
937 8 310
938 12 4188
939 3 327
940 14 27423116
941 4 481390
942 14 153944183
943 9 26505
944 8 1981164173
945 3 93513
946 10 186602
947 16 98439821
948 10 19789371
949 16 2004730220
950 16 13
951 5 4
952 7 282
953 13 68618170
954 4 51435
955 8 51824997
956 8 36032
957 3 770059
958 7 453693361
959 15 1
960 6 494
961 5 107499075
962 12 10
963 14 155521816
964 5 5
965 11 31109656
966 15 234
967 9 5
968 15 4223178
969 7 828637476
970 5 127327665
971 5 1825961333
972 11 777551
973 3 97
974 9 24269411
975 6 685
976 8 266264
977 12 7476410
978 15 26955
979 8 234869
980 7 1726
981 6 8030024
982 5 21
983 10 2306
984 4 267499347
985 14 6773538
986 13 1030397
987 7 29450154
988 6 10
989 6 48
990 12 13818002
991 13 206
992 6 1408746
993 14 5
994 16 2109912189
995 13 39831625
996 16 6
997 13 7
998 14 9
999 5 430263280
1000 5 75366236
