A new pizza shop has opened on Universe North Street. This shop specializes in pizzas topped with Chinese sausage, affectionately known by customers as the "Sausage Pizza Shop." While this fusion of Eastern and Western culinary styles sounds unconventional, customers who have tasted the sausage pizza have praised it highly, attracting a large crowd of diners.

In addition to its unique toppings, the Sausage Pizza Shop's Wi-Fi password is also a key to its popularity. The menu states: "Our Wi-Fi password is

$$ \sum_{i=1}^L \sum_{j=1}^L C^{\left|LCPS\left(s_i, s_j\right)\right|} \bmod{P}, $$

where $LCPS\left(s_i, s_j\right)$ denotes the Longest Common Prefix-Suffix of $s_i$ and $s_j$, which is the longest string that is both a prefix of $s_i$ and a suffix of $s_j$ (it may be empty or the entire string). The strings $s_1, \cdots, s_L$ change every day, and the waiter will provide the strings used for that day's Wi-Fi password after you order. Every day, one lucky customer will be randomly selected from the first 100 customers who connect to the Wi-Fi to receive their meal for free."

You plan to dine at this shop with your friends next week, so you want to design an algorithm to quickly calculate the shop's Wi-Fi password.

Input

Read data from standard input.

The first line contains three positive integers $L, C, P$, representing the number of strings, the base, and the modulus, respectively. It is guaranteed that $1\le L\le 3\times 10^6$ and $2\le C < P < 2^{30}$.

The next $L$ lines each contain a string $s_i$ consisting only of lowercase letters. It is guaranteed that $1\le \left|s_i\right| \le 3\times 10^6$ and $\sum_{i=1}^L \left|s_i\right| \le 3\times 10^6$.

Output

Write to standard output.

Output a non-negative integer representing the Sausage Pizza Shop's Wi-Fi password.

Examples

Input 1

4 2 378323747
shop
pizza
piazza
pizzala

Output 1

286

Note 1

For $1\le i,j\le 4, i\ne j$,

• $LCPS($ pizza $,$ shop $)=LCPS($ piazza $,$ shop $)=LCPS($ pizzala $,$ shop $)=$ p；

• $LCPS($ pizzala $,$ pizza $)=$ pizza；

• All other $LCPS\left(s_i, s_j\right)=\varepsilon$.

Therefore, the corresponding Wi-Fi password is

$$ 2^4 + 2^0 + 2^0 + 2^0 + 2^1 + 2^5 + 2^0 + 2^0 + 2^1 + 2^0 + 2^6 + 2^0 + 2^1 + 2^5 + 2^0 + 2^7 = 286. $$

Input 2

9 99 998244353
asap
peace
piece
pizza
sapiens
dazzling
andromeda
sakurasaku
kokorosaku

Output 2

161369438

Note

The Sausage Pizza Shop uses a top-secret recipe when making its pizzas. Please do not attempt to imitate it without professional guidance.