시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 2 2 2 100.000%

## 문제

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:

• 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

12 + 12 + 12 + 12 + 22 + 22 = 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