/home/toolbox/public_html/solutions/101/10179/u1.in
1 1
2 999999999
3 69347
4 415766464
5 174051500
6 622658676
7 83467
8 88934
9 71024
10 56714
11 1505
12 3075
13 78549
14 690591244
15 19497
16 882000767
17 48434
18 79817
19 40179
20 342801563
21 43495
22 714900869
23 765090620
24 85431
25 92724
26 730931454
27 95544
28 32226
29 34800
30 59346
31 33426
32 34649
33 13241
34 57986
35 71580
36 433334263
37 50734
38 615840159
39 11860
40 26979
41 624619014
42 54809
43 252928238
44 32091
45 24057
46 10578
47 26280
48 30348
49 68265
50 900854360
51 97426
52 673757576
53 969365624
54 29005
55 11049
56 15681
57 30637
58 798338397
59 116008353
60 972394705
61 760417440
62 39726
63 63419
64 9661
65 95970
66 1202
67 18609
68 96229
69 957440995
70 87360
71 28576
72 7088
73 68800
74 71799
75 18752
76 7399
77 16742
78 769705643
79 78176
80 4507
81 341861581
82 45903
83 93829
84 25425
85 91822
86 14856
87 48101
88 3552
89 758838866
90 12188
91 383782441
92 15727
93 64534
94 73763
95 27077
96 183026254
97 95205
98 7440
99 19283
100 17426
101 349075259
102 20023367
103 76601
104 62446
105 10719
106 12496
107 2854
108 608064003
109 78550
110 5609
111 93260
112 42968
113 366487135
114 23240988
115 585958678
116 144652738
117 69930
118 564813885
119 1152
120 96634
121 128135500
122 82754
123 75837
124 4513
125 68561
126 456638104
127 81302
128 20648
129 92383
130 22036
131 37114
132 38541
133 36386
134 96627668
135 96046
136 56267
137 92023
138 53361
139 76399
140 855461656
141 874388034
142 6367
143 74147
144 154642863
145 14310
146 475544273
147 99954
148 18182
149 624428121
150 193256484
151 45168
152 91704
153 30100619
154 546049669
155 31762
156 63362
157 27014
158 64701
159 66995
160 23248
161 74847
162 509409707
163 779937609
164 85584
165 70281
166 935241399
167 58738
168 610999901
169 72772
170 41881
171 54286
172 5122
173 702200213
174 63730
175 226208038
176 90839
177 63757
178 78497
179 34461
180 945070472
181 81693
182 62802
183 1022
184 691361597
185 74322
186 84842
187 18267
188 21195
189 229060263
190 81664
191 59757
192 84707
193 51515
194 37904
195 85595
196 44786
197 28862
198 71443
199 856530567
200 33306
201 30545
202 6894
203 31591
204 76916
205 14039
206 77657
207 56973
208 89418
209 21606
210 498757779
211 15173
212 61835
213 67478
214 627760260
215 53747
216 42460
217 91489
218 72603
219 860393572
220 85992
221 10818
222 1951
223 19724
224 445377596
225 35721
226 85007
227 911945860
228 95133
229 22799
230 40553
231 95170
232 71374
233 8825
234 63689
235 941536296
236 68670
237 55178
238 69437
239 43036
240 81996
241 710237112
242 50535
243 71868
244 417802174
245 52752
246 98830
247 12620
248 620656176
249 3544
250 13721
251 17534
252 52352
253 96748
254 616555545
255 15723
256 67909
257 78126
258 23883
259 6395
260 50613
261 28470
262 56171
263 94870
264 59819
265 78396
266 43374
267 88063
268 68741
269 25179
270 34488
271 261358279
272 41699
273 76526
274 23811
275 36981
276 69507068
277 46076
278 82289
279 90947
280 663423042
281 984115597
282 55082
283 583070068
284 30182
285 25789
286 47585
287 34059
288 85812
289 10963
290 843099314
291 423363724
292 74466
293 35429
294 96262
295 28290
296 90156
297 85009
298 528281358
299 75027
300 56508
301 970
302 76217
303 29778
304 423717459
305 923770295
306 77024
307 43503
308 676757587
309 733705433
310 11228
311 22503
312 766830756
313 79857
314 55052
315 27591
316 64360
317 41347
318 13048
319 603874306
320 42436
321 40807
322 40107
323 80088
324 51326
325 33802
326 280565469
327 241558524
328 82940
329 71451
330 37508
331 71647
332 85298
333 34360
334 69612
335 49566
336 20162
337 167677790
338 57908
339 16379
340 6226
341 88219
342 770951470
343 84273
344 774489119
345 86853
346 32945
347 2803
348 43813
349 32108
350 93759
351 63968
352 72219
353 31202
354 19409
355 46982
356 72795
357 83714
358 2413
359 308965916
360 47857
361 36578
362 70238
363 36800
364 74866
365 20091
366 36629
367 30965
368 14129
369 25416
370 34499
371 40573
372 774843379
373 26911
374 744856986
375 13329
376 18796
377 4652
378 39232
379 97729
380 44359
381 35535
382 44279
383 14459
384 717966543
385 143442117
386 41069
387 9294
388 16365
389 57335
390 64849
391 35538
392 686971248
393 55745
394 19467
395 75955
396 84500
397 49367
398 76591
399 87075
400 256835314
401 35240
402 852587101
403 799043359
404 25433
405 55843
406 83617
407 21337
408 98046
409 40800
410 60797977
411 4256
412 75977
413 238615756
414 86161
415 880300776
416 22968
417 22226
418 72789
419 75921
420 87692
421 3014
422 931481183
423 11991
424 63146
425 74726
426 51434
427 86201
428 96591
429 372727661
430 44991
431 15319
432 57800
433 47764
434 26943
435 34793
436 933027095
437 12268
438 99023
439 82517
440 3183
441 44889
442 78788
443 225972659
444 24741
445 34337
446 88260
447 97806
448 215171367
449 624522697
450 87278
451 6344
452 956027390
453 612749371
454 63112
455 29335
456 962286228
457 57917
458 31647
459 14591
460 67663
461 36327
462 614870625
463 493786227
464 52252845
465 450049778
466 644818180
467 74798
468 88333
469 43041
470 26160
471 39171
472 22690
473 77806
474 8924
475 634517447
476 50007298
477 639404792
478 693454450
479 437819692
480 54009
481 66907
482 428445387
483 484891665
484 399184733
485 69311
486 205396097
487 37598
488 28201
489 98261
490 711146983
491 75287
492 9270
493 52383
494 26189
495 81578
496 98703
497 98432
498 46629
499 22876
500 620898980
501 943321333
502 25923
503 13338
504 55973
505 398188896
506 52126
507 89190
508 959539518
509 93040
510 93289
511 81463
512 405725229
513 16381
514 86389
515 22442
516 165120449
517 1495
518 52275
519 822500875
520 83424
521 57504
522 35494953
523 830979176
524 742887735
525 926223049
526 8766
527 44618
528 739501345
529 26311
530 71399
531 99044
532 259711810
533 479253791
534 31648
535 348206141
536 974101660
537 41666
538 71318
539 19660
540 7539
541 50988
542 77528
543 35771
544 94134
545 66765
546 56645
547 473553722
548 318583477
549 73479
550 53490
551 46815
552 42201
553 49053298
554 36520
555 777783081
556 80130
557 93938
558 15689
559 32616
560 49605
561 34391
562 406541329
563 52605
564 1978
565 2623
566 234709659
567 69121
568 750792529
569 16462
570 54741
571 73080
572 34028
573 36220
574 68076
575 87920
576 158525890
577 42351
578 229961285
579 75859
580 74737
581 58863
582 46697
583 80510
584 7286
585 8964
586 95850
587 89523
588 435799289
589 47921
590 26930
591 82809
592 48410
593 66402
594 78130
595 66396
596 9481
597 60427
598 54090
599 68389
600 54015
601 79911
602 115626819
603 90866
604 59280
605 24188
606 70019
607 99194
608 723408615
609 43873
610 45952
611 788527188
612 76485
613 12143
614 27587117
615 234584058
616 26811
617 4221
618 15151
619 5542
620 76884
621 45904
622 56908
623 51363
624 45078
625 57977
626 68585
627 522739700
628 7628
629 497473517
630 20923
631 56098
632 938143073
633 34193
634 3531
635 15556
636 5420
637 23220
638 76680
639 75934
640 68121
641 40699
642 69941
643 87570
644 69625
645 66387
646 89479
647 917578611
648 955516051
649 411177574
650 63435
651 94944
652 884601118
653 44648
654 10767
655 38151
656 14914
657 81074
658 570352967
659 76861
660 783304646
661 40180
662 91438
663 391215044
664 83445
665 35511
666 56783
667 7235
668 55727
669 37360
670 32520
671 1936
672 63926
673 97796
674 72795
675 72054
676 55861
677 125112040
678 1246
679 203486097
680 25618
681 8312
682 61118
683 107801738
684 17025
685 26241
686 14337525
687 539485462
688 645669650
689 15415
690 65847
691 146236310
692 908821243
693 57386
694 5640
695 4163
696 82626
697 20651
698 94593
699 22669
700 463091281
701 806468460
702 87448
703 98141
704 64816
705 76372
706 64914
707 93777
708 764386455
709 625199763
710 45676
711 31436
712 75642
713 350234804
714 607081116
715 51076
716 70340
717 360319108
718 92431
719 85892
720 69853
721 85035
722 85933
723 908608249
724 67349
725 36027
726 58346
727 56238
728 511135975
729 55460
730 76229
731 77324
732 31167
733 18777
734 82599
735 95207
736 48408
737 52151
738 13767
739 46118
740 63917
741 70903
742 768133004
743 68845
744 35350
745 8251
746 33181
747 38537
748 28380
749 415232035
750 60118
751 42213
752 98637376
753 7910
754 489354578
755 238772326
756 732133497
757 66412
758 27428121
759 93296
760 71016
761 865362345
762 59531
763 855492347
764 22578
765 13727
766 82921
767 83465
768 297049563
769 55383
770 96852
771 80297
772 669621798
773 37635
774 14544
775 336216405
776 30181
777 921943167
778 288872130
779 8491
780 75492
781 787922968
782 65100
783 73312
784 92191
785 392912057
786 65074
787 893365200
788 98030
789 843848736
790 32092
791 27316
792 2199
793 634330619
794 2645
795 61608
796 84793
797 74371
798 939241989
799 802260031
800 68305
801 34749
802 729644898
803 78818019
804 78779
805 64864
806 780250140
807 80509
808 59206
809 25394527
810 63350
811 66587
812 41289
813 859903327
814 250129434
815 96405928
816 62984
817 6044
818 78202
819 13505
820 825938550
821 85718
822 315787516
823 58243
824 21557
825 226717425
826 53127
827 78964
828 326167679
829 97350
830 23782
831 1184
832 87721
833 88582
834 93417
835 97647
836 835089942
837 26160
838 50763
839 335008874
840 20531
841 26463
842 58005
843 77302
844 722742879
845 28718
846 28233
847 796528061
848 17289
849 78091
850 36839
851 67930
852 620
853 51476
854 94293
855 20429
856 85357
857 89436
858 41486
859 876727222
860 673
861 22536
862 64510
863 38314
864 168391347
865 55089
866 2767
867 1003
868 69044
869 17603
870 85934
871 47436
872 50126
873 92919
874 784182416
875 22511
876 23788
877 688479995
878 86672
879 601997942
880 89897
881 170597599
882 556
883 3344
884 555455188
885 579627867
886 88527
887 19416
888 7995
889 564934524
890 1600
891 85676
892 44583
893 37294
894 1841
895 356935332
896 70171
897 272650293
898 6931
899 86802
900 82128
901 90796
902 413546569
903 32102
904 655255323
905 92122
906 36611
907 67680
908 345675606
909 662098760
910 94648
911 52445
912 40655
913 71176410
914 11324
915 11491
916 834673761
917 4829
918 50326
919 89875
920 19498
921 89730
922 598248070
923 273689230
924 9301
925 20376
926 30673
927 752628921
928 642548953
929 190459706
930 91784
931 9798
932 89740
933 34942
934 97082
935 14131
936 83714
937 79633
938 89043
939 42938
940 3716
941 28926
942 61357
943 909609445
944 9749
945 81789
946 82464
947 51012
948 34772
949 93007
950 53574
951 25744
952 277761187
953 1411
954 27937
955 39905
956 258132460
957 13828
958 46853
959 685189959
960 67214
961 671575006
962 12204
963 40260
964 28718
965 79721
966 10046
967 56404
968 1158
969 46836
970 3778
971 947032002
972 8018
973 76252785
974 29708
975 81063
976 33301
977 95982
978 79822
979 55983
980 42232
981 1085
982 8482
983 931
984 89356
985 79409
986 84611
987 93103
988 50352
989 83844
990 183485433
991 35216
992 78845
993 92443
994 47007
995 973114489
996 97494
997 325479279
998 340836486
999 21869
1000 54267
1001 0
1002