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

輸入格式

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

輸出格式

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

範例輸入 1

50 CBA

範例輸出 1

5

範例輸入 2

5 BaaC

範例輸出 2

2

範例輸入 3

5 BAAC

範例輸出 3

1

提示

本題出自 2018 TOI Pre (TIOJ 2052)