TopCoder

User's AC Ratio

73.9% (34/46)

Submission's AC Ratio

22.9% (52/227)

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

No. Testdata Range Score
1 0~6 10
2 7~16 20
3 17~26 30
4 27~39 40

Testdata and Limits

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