題目描述

對於一個長度為 𝑛 的字串 𝑠，如果該字串是一個回文字串，則對於所有整數 𝑖 (1 ≤ 𝑖 ≤ 𝑛) 均有 𝑠[𝑖] = 𝑠[𝑛 − 𝑖 + 1]。例如：bob 是一個回文字串，而 agd 不是。

小 A 有一個僅由英文字母組成的字串 𝑠，他希望把這個字串的所有大階英文字母都改為任意的小階英文字母，並令這個字串成為一個回文字串。

小 A 希望你幫他計算出，有多少個修改後的字串滿足這個要求。另外，小 A 怕這個數字太大，所以他讓你把這個答案對一個正整數 𝑝 取模。其中，mod 是取餘運算，𝑎 mod 𝑏 (𝑎 對 𝑏 取模) 即為 𝑎 除以 𝑏 所得的餘數。

輸入格式

你需要在標準輸入 (stdin) 讀入數據。

本題有多組測試數據。

輸入的第一行包含一個整數 𝑐，表示子任務編號。𝑐 = 0 表示該測試點為樣例。

第二行包含一個正整數 𝑇，表示測試數據組數。

對於每組測試數據：

• 第一行包含一個字串 𝑠。
• 第二行包含一個正整數 𝑝。

輸出格式

你需要在標準輸出 (stdout) 輸出答案。

對於每組測試數據：

• 輸出一行，一個整數表示答案。

Samples

0
3
abACa
10
Abaka
10
aBBsbA
10

6
0
1

提示

【樣例 1 解釋】

對於第一組測試數據，滿足要求的字串有：ababa、abbba、abcba、…、abzba，

共 26 個字串滿足要求。對 𝑝 = 10 取餘後應輸出 6。

對於第二組測試數據，沒有字串滿足要求，答案為 0。

對於第三組測試數據，滿足要求的字串只有 abssba，答案為 1。對 𝑝 = 10 取

餘後應輸出 1。

【數據範圍】

記 𝑛 為字串 𝑠 的長度。

對於所有測試數據，保證：

• 𝑇 ≤ 10
• 𝑛 ≤ 10⁶
• 𝑝 ≤ 10⁶
• 字串 𝑠 僅由英文字母組成。

子任務	分數	𝑛 ≤	特殊性質
1	5	5	A
2	20	5	無
3	5	106	A
4	10	106	B
5	60	106	無

特殊性質 A：字串 𝑠 僅由小階英文字母組成。

特殊性質 B：字串 𝑠 僅由大階英文字母組成。

原始資料

• Zero1 題號：b519
• Hydro 題號：Z1519
• Locale：zh_TW
• Display：open