Zadanie

Kreatívny názov

Počet bodov: 100

Nájdite počet reťazcov \(r\) s nasledujúcimi vlastnosťami: - \(r\) má dĺžku \(n\) písmen, pričom každé písmeno patrí do abecedy s veľkosťou \(k\) (napr. \(k = 26\) pre anglickú abecedu) - \(r\) je palindróm - pre každé \(l\) medzi \(2\) a \(n-1\) (vrátane) platí, že prefix \(r\) s dĺžkou \(l\) nie je palindróm

Keďže tento počet palindrómov môže byť veľmi veľký, stačí, ak nájdete jeho zvyšok po delení prvočíslom \(p\).

(Palindróm je reťazec písmen, ktorý prečítame rovnako odpredu aj odzadu, napr. velipsespilev. Prefix reťazca s dĺžkou \(l\) sa skladá z \(l\) písmen na jeho začiatku v nezmenenom poradí.)

Vstup a výstup

Na prvom riadku vstupu je jedno celé číslo \(t\) – počet samostatných testov.

Nasleduje \(t\) riadkov. Každý z nich obsahuje tri celé čísla \(n\), \(k\) a \(p\) popisujúce jeden z testov.

Pre každý test vypíšte jeden riadok a na ňom jedno celé číslo – počet reťazcov s danými vlastnosťami modulo \(p\).

Obmedzenia

Platí \(1 \le t \le 10\) a \(1 \le n, k \le 10^5\). Je garantované že \(p\) je prvočíslo, pre ktoré platí \(10^8 \le p \le 10^9+9\).

Je niekoľko testovacích sád. V niektorých sadách je \(n \le 15\) a \(k \le 6\). V iných je veľké \(k\), ale postupne rastie \(n\); v približne polovici z týchto sád je \(n \le 2000\). Objaví sa aj sada, kde \(k = 2\).

Príklad

Input:

4
1 10 1000000009
2 2 1000000009
4 3 1000000009
34 5 1000000009

Output:

10
2
6
912957714