【模板】模意义下的乘法逆元

题目背景

这是一道模板题。

题目描述

给定正整数 $n,p$，求 $[1,n]$ 中所有整数在模 $p$ 意义下的乘法逆元。

$a$ 模 $p$ 的乘法逆元定义为 $ax\equiv1\pmod p$ 的解。

输入格式

一行两个正整数 $n,p$。

输出格式

输出 $n$ 行，其中第 $i$ 行表示 $i$ 在模 $p$ 下的乘法逆元。

输入样例 #1

10 13

输出样例 #1

1
7
9
10
8
11
2
5
3
4

输入样例 #2

200 1000000007

输出样例 #2

1
500000004
333333336
250000002
400000003
166666668
142857144
125000001
111111112
700000005
818181824
83333334
153846155
71428572
466666670
562500004
352941179
55555556
157894738
850000006
47619048
409090912
739130440
41666667
280000002
576923081
370370373
35714286
758620695
233333335
129032259
281250002
939393946
676470593
628571433
27777778
621621626
78947369
717948723
425000003
658536590
23809524
395348840
204545456
822222228
369565220
404255322
520833337
448979595
140000001
784313731
788461544
56603774
685185190
763636369
17857143
385964915
879310351
50847458
616666671
688524595
564516133
15873016
140625001
30769231
469696973
686567169
838235300
579710149
814285720
98591550
13888889
410958907
310810813
93333334
539473688
831168837
858974365
202531647
712500005
123456791
329268295
84337350
11904762
670588240
197674420
252873565
102272728
415730340
411111114
164835166
184782610
43010753
202127661
231578949
760416672
268041239
724489801
646464651
570000004
940594066
892156869
572815538
394230772
209523811
28301887
224299067
342592595
9174312
881818188
873873880
508928575
893805316
692982461
147826088
939655179
239316241
25423729
478991600
808333339
438016532
844262301
886178868
782258070
856000006
7936508
480314964
570312504
798449618
515384619
190839696
734848490
165413535
843283588
274074076
419117650
58394161
789855078
604316551
407142860
134751774
49295775
832167838
506944448
151724139
705479457
149659865
655405410
530201346
46666667
483443712
269736844
594771246
915584422
625806456
929487186
343949047
601265827
685534596
856250006
962732926
561728399
116564418
664634151
587878792
42168675
5988024
5952381
242603552
335294120
795321643
98837210
791907520
626436786
325714288
51136364
683615824
207865170
435754193
205555557
933701664
82417583
562841534
92391305
524324328
521505380
577540111
601063834
338624341
615789478
439790579
380208336
694300523
634020623
343589746
862244904
969543154
823232329
507537692
285000002

输入样例 #3

300 1000000007

输出样例 #3

1
500000004
333333336
250000002
400000003
166666668
142857144
125000001
111111112
700000005
818181824
83333334
153846155
71428572
466666670
562500004
352941179
55555556
157894738
850000006
47619048
409090912
739130440
41666667
280000002
576923081
370370373
35714286
758620695
233333335
129032259
281250002
939393946
676470593
628571433
27777778
621621626
78947369
717948723
425000003
658536590
23809524
395348840
204545456
822222228
369565220
404255322
520833337
448979595
140000001
784313731
788461544
56603774
685185190
763636369
17857143
385964915
879310351
50847458
616666671
688524595
564516133
15873016
140625001
30769231
469696973
686567169
838235300
579710149
814285720
98591550
13888889
410958907
310810813
93333334
539473688
831168837
858974365
202531647
712500005
123456791
329268295
84337350
11904762
670588240
197674420
252873565
102272728
415730340
411111114
164835166
184782610
43010753
202127661
231578949
760416672
268041239
724489801
646464651
570000004
940594066
892156869
572815538
394230772
209523811
28301887
224299067
342592595
9174312
881818188
873873880
508928575
893805316
692982461
147826088
939655179
239316241
25423729
478991600
808333339
438016532
844262301
886178868
782258070
856000006
7936508
480314964
570312504
798449618
515384619
190839696
734848490
165413535
843283588
274074076
419117650
58394161
789855078
604316551
407142860
134751774
49295775
832167838
506944448
151724139
705479457
149659865
655405410
530201346
46666667
483443712
269736844
594771246
915584422
625806456
929487186
343949047
601265827
685534596
856250006
962732926
561728399
116564418
664634151
587878792
42168675
5988024
5952381
242603552
335294120
795321643
98837210
791907520
626436786
325714288
51136364
683615824
207865170
435754193
205555557
933701664
82417583
562841534
92391305
524324328
521505380
577540111
601063834
338624341
615789478
439790579
380208336
694300523
634020623
343589746
862244904
969543154
823232329
507537692
285000002
228855723
470297033
108374385
946078438
131707318
286407769
526570052
197115386
832535891
604761909
90047394
514150947
32863850
612149537
79069768
671296301
875576043
4587156
470319638
440909094
950226251
436936940
125560539
754464291
364444447
446902658
35242291
846491234
711790398
73913044
277056279
969827593
90128756
619658124
880851070
512711868
67510549
239495800
280334730
904166673
406639007
219008266
707818935
922131154
89795919
443089434
165991904
391129035
28112450
428000003
912350604
3968254
339920951
240157482
556862749
285156252
70038911
399224809
517374521
757692313
417624524
95419848
836501907
367424245
611320759
582706771
138576780
421641794
743494429
137037038
450184505
209558825
388278391
529197084
752727278
394927539
252707583
802158279
681003589
203571430
718861215
67375887
650176683
524647891
77192983
416083919
808362375
253472224
961937723
575862073
756013751
852739732
522184304
574829936
210169493
327702705
215488217
265100673
441471575
523333337

数据范围

所有数据满足 $1 \leq n \leq 3 \times 10 ^ 6$，$n < p < 20000528$。