시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB333100.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