Module: Hashing


Problem

1/8

double string hash

Theory Click to read/hide

Error

Problem

You are given t queries, in each of which you are given a string s consisting of lowercase Latin letters, a number p and a number mod.
For each query, compute a polynomial hash modulo base p of the string that is the string s, where each letter is duplicated. That is, if s = "isaac", then you need to calculate the hash from the string "iissaaaacc".

Input:
The first line contains the number t - the number of requests.
Then there are t lines, each containing space-separated s (1 <= |s| <= 20), p (1 <= p <= 105) and mod ( 1 <= mod <= 108).

Output:
Print the responses to the queries, each on a separate line.

Example:
 
Input Output
2
isaac 12345 87654321
newton 54321 12345678
8829000
9632318