Any string of length (n) has (2^n) subsequences, which are the strings obtained by deleting some subset of the characters. But these subsequences may not all be distinct. For example, the string “zoo” has only 6 distinct subsequences:</p>

• the subsequences “z”, “oo”, and “zoo” appear only once,
• the empty subsequence appears only once,
• and the subsequences “o” and “zo” each appear twice.

Suppose a string (S) has (k) distinct subsequences, and that the (i)th one appears (f_i) times. Then the repetitivity of (S) is defined as (\sum_{i=1}^{k}{f_i^2}). For example, the repetitivity of “zoo” is

1² + 1² + 1² + 1² + 2² + 2² = 12.

입력 형식

Each test case contains a line containing the string (S) (with length at most 10 000), followed by a line containing a single integer (M) ((2 \le M \le 1 000 000 000)). You may assume that (S) only contains characters with ASCII codes between 33 and 126 inclusive (these are all printable, nonwhitespace characters).

출력 형식

The output should consist of a single line, containing the repetitivity of (S), modulo (M).

예제 입력 1

zoo
10

예제 출력 1

2

예제 입력 2

@#$%
1000000

예제 출력 2

16