TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P4783
  • Problem
  • P4783【SDOI2018】反回文串
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 2s,512m
    Description

    「回文串什么的最讨厌了……」

    小 Q 讨厌任何形式的回文串:

    1. 如果一个字符串从左往右读和从右往左读是一样的,那么小 Q 讨厌它;例如 aaaba

    2. 对于一个字符串来说,若将某个前缀子串移除并拼接到字符串的尾部,能得到一个小 Q 讨厌的字符串,那么小 Q 也会讨厌原来的这个字符串;例如 aabbaa

    现在问题来了,如果任意字符串只可以由 \(k\) 种已知的字符组成(也就是说字符集的大小为 \(k\)),那么长度为 \(n\) 的所有字符串里,有多少字符串是小 Q 讨厌的?

    答案可能很大,你只需要给出答案对 \(p\) 取模后的值。

    Input Format

    第一行包含一个正整数 \(T\),表示有 \(T\) 组测试数据。

    接下来 \(T\) 行,每行描述一组测试数据,包含三个正整数 \(n\), \(k\)\(p\)

    Output Format

    对于每组测试数据,输出一行,包含一个整数,表示答案对 \(p\) 取模的值。

    Sample Input

    10
    1 1 1000000001
    2 2 1000000003
    3 2 1000000005
    3 3 1000000007
    4 2 1000000009
    4 3 1000000011
    4 4 1000000013
    5 5 1000000015
    7 7 1000000017
    9 9 1000000019

    Sample Output

    1
    2
    8
    21
    6
    15
    28
    605
    16765
    530937

    Hint

    对于 $30%$ 的数据,有 $1 \leq n \leq 10^{10}$。
    对于 $60%$ 的数据,有 $1 \leq n \leq 10^{14}$。
    对于 $100%$ 的数据,有 $1 \leq T \leq 10, 1 \leq n \leq 10^{18}, 1 \leq k \leq n, 109 \leq p \leq 2{30}$。