Rəng

Muncuqların n rəngi bir-birinə dövrü şəkildə n muncuqla birləşdirilib (n ≤ 10^9). Sizdən, bu muncuqlardan əldə edilə biləcək müxtəlif kombinasiyaların sayını hesablamaq tələb olunur. Burada, muncuqda bütün n rənglərdən istifadə etmək məcburi deyil. Muncuğun mərkəzi ətrafında döndərilməsi nəticəsində yaranan təkrarlara məhəl qoyulmamalıdır.

Cavabı p modulunda təqdim edin.

Giriş verilənləri

Birinci sətir testlərin sayını x (x ≤ 3500) göstərir. Sonrakı x sətirin hər biri iki ədəd n və p (1 ≤ n ≤ 10^9, 1 ≤ p ≤ 30000) ehtiva edir.

Çıxış verilənləri

Hər test üçün cavabı ayrı-ayrı sətirlərdə təqdim edin.

Nümunələr