User's AC Ratio

73.2% (30/41)

Submission's AC Ratio

22.9% (46/201)

Description

$N$個可重複的英文字母排成一列,共有幾種排法?比如說,兩個A一個B一個C排成一列共有12種排法,依照字典排序法依序如下:AABC、AACB、ABAC、ABCA、ACAB、ACBA、BAAC、BACA、BCAA、CAAB、CABA、CBAA。
現在給定一個排序$\pi$,請問$\pi$是該些字母排列中的第幾個?上述中第0個為AABC,第1個為AACB,而BAAC是兩個A一個B一個C的排列中依照字典排序法中的第6個。若$\pi$是該些字母排列中的第$K$個,為方便輸出,給定一個整數$D$,輸出$K$除以$D$的餘數。

Input Format

輸入只有一行,先有一個整數$D(1 < D < 10000)$,再有一串可重複字母的英文字串$S$,中間以空白隔開。

子任務(測資) 額外限制 分數
1 (0~6) 字母$S$字母不重複,長度最多為5 10
2 (7~16) 字串$S$字母不重複,長度最多為52 20
3 (17~26) 字串$S$字母可重複,長度最多為10 30
4 (27~39) 字串$S$字母可重複,長度最多為1024 40

Output Format

假設字串$S$為該些字母的排列中的第$K$個,輸出$K$除以$D$的餘數。

Sample Input

Sample Input #1
50 CBA

Sample Input #2
5 BaaC

Sample Input #3
5 BAAC

Sample Output

Sample Output #1
5

Sample Output #2
2

Sample Output #3
1

Hints

Problem Source

2018 TOI入營考pB

Subtasks

For Testdata: 0 ~ 6, Score: 10
For Testdata: 7 ~ 16, Score: 20
For Testdata: 17 ~ 26, Score: 30
For Testdata: 27 ~ 39, Score: 40
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 262144 262144
1 1000 262144 262144
2 1000 262144 262144
3 1000 262144 262144
4 1000 262144 262144
5 1000 262144 262144
6 1000 262144 262144
7 1000 262144 262144
8 1000 262144 262144
9 1000 262144 262144
10 1000 262144 262144
11 1000 262144 262144
12 1000 262144 262144
13 1000 262144 262144
14 1000 262144 262144
15 1000 262144 262144
16 1000 262144 262144
17 1000 262144 262144
18 1000 262144 262144
19 1000 262144 262144
20 1000 262144 262144
21 1000 262144 262144
22 1000 262144 262144
23 1000 262144 262144
24 1000 262144 262144
25 1000 262144 262144
26 1000 262144 262144
27 1000 262144 262144
28 1000 262144 262144
29 1000 262144 262144
30 1000 262144 262144
31 1000 262144 262144
32 1000 262144 262144
33 1000 262144 262144
34 1000 262144 262144
35 1000 262144 262144
36 1000 262144 262144
37 1000 262144 262144
38 1000 262144 262144
39 1000 262144 262144