ACT 1: Ash Counting Trees

অ্যাশ কেচামের একটা অদ্ভুত রুটেড ট্রি আছে (ট্রি ডেটা স্ট্রাকচার সম্পর্কে ধারণা না থাকলে Notes সেকশন পড়তে পারো)। ট্রি-টার নোড (ভার্টেক্স) অসীম সংখ্যক। প্রত্যেক নোডের $K$-টা চাইল্ড নোড আছে। অ্যাশ এ ধরণের ট্রি-কে $K$-চাইল্ড ট্রি নামে ডাকে। তার মানে, যদি $K = 2$ হয়, এটি একটি 2-চাইল্ড ট্রি এবং ট্রি-টা একটা অসীম নোড সংখ্যক বাইনারি ট্রি। একইভাবে 3-চাইল্ড ট্রি একটা অসীম নোড সংখ্যক টার্নারি ট্রি। শুরুতে ট্রি-এর সব নোড ফাঁকা থাকে।

অ্যাশ এরকম একটা ট্রি-এর $N$-টা নোড কিছু ধনাত্বক পূর্ণসংখ্যা দ্বারা লেবেল করতে চায়, নিম্নোক্ত নিয়মগুলো অনুসরণ করে:
১) একটা ট্রি নোড $U$-কে তখনই লেবেল করা যাবে যখন তার প্যারেন্ট নোডকে ইতিমধ্যে লেবেল করা হয়ে গেছে, অথবা নোডটা ট্রি-এর রুট নোড।
২) একটা নোড $V$ ভ্যালু দ্বারা তখনই লেবেল করা যাবে যখন এর আগে লেবেল করা নোডে $V-1$ বসানো হয়েছিল। যদি এর আগে কোন নোড লেবেল না করা হয়ে থাকে, তাহলে $V = 1$ ব্যবহার করতে হবে।
৩) একটা নোড একবারের বেশি লেবেল করা যাবে না।

অ্যাশ একটা ফাংশন $F(N,K)$ নিম্নোক্তভাবে সংজ্ঞায়িত করেছে।
$F(N, K)$ = কয়টা $K$-চাইল্ড ট্রি পাওয়া সম্ভব যদি উপরোক্ত নিয়মানুসারে অ্যাশ $N$-টা নোড লেবেল করে।

উদাহরণস্বরূপ, $F(3, 2) = 6$ এবং এই 6টা ট্রি নিচের ছবিতে দেখানো হলো।

সে প্রথমে $F(N, K)$-কে $P^Z$ দ্বারা ভাগ করে যেন $F(N, K)$-কে $P^Z$ নিঃশেষে ভাগ করে এবং $Z$ সর্বোচ্চ হয়। অবশেষে সে নিচের এটি পায়:

তোমার কাজ হলো অ্যাশকে এটার মান বের করতে সাহায্য করা।

সহজ ভাষায়, তোমাকে $N$, $K$, $P$ এবং $Q$ দেওয়া হবে, তোমাকে $\frac{\displaystyle F(N, K)}{\displaystyle P^Z} \pmod {P^Q}$ বের করতে হবে।

Input

ইনপু্টের প্রথম লাইনে একটা ইন্টেজার (পূর্ণসংখ্যা) $T$ থাকবে যা টেস্ট কেসের সংখ্যা প্রকাশ করে। এরপরের $T$-টা লাইন টেস্ট কেসগুলোকে বর্ণনা করবে।

প্রত্যেক টেস্ট কেসে চারটা স্পেস-সেপারেটেড ইন্টেজার $N$, $K$, $P$ এবং $Q$ দেওয়া থাকবে (ওই টেস্টকেসের লাইনে)।

Constraints

$1 \leq T \leq 100$
$1 \leq P \leq 10^6$
এটা নিশ্চিত যে সব সাবটাস্কেই $P$ একটি মৌলিক সংখ্যা।

Subtask 1 (5 points)

$1 \leq N, K \leq 10^{6}$
$Q = 1$

Subtask 2 (15 points)

$1 \leq N \leq 10^{12}$
$1 \leq K \leq 2$
$Q = 1$

Subtask 3 (35 points)

$1 \leq N \leq 10^{12}$
$1 \leq K \leq 10^6$
$Q = 1$

Subtask 4 (45 points)

$1 \leq N \leq 10^{12}$
$1 \leq K \leq 10^6$
$1 \leq P^Q \leq 10^6$
$Q \geq 1$

Output

প্রত্যেক টেস্ট কেসের জন্য, একক একটি লাইনে $\frac{\displaystyle F(N, K)}{\displaystyle P^Z} \pmod {P^Q}$ প্রিন্ট করো। আরো বিস্তারিত জানতে উপরোক্ত প্রবলেম স্টেটমেন্ট পড়ো।

Sample

Input	Output
7 2 2 5 1 3 2 7 1 3 2 5 1 3 2 2 1 3 2 3 1 3 3 17 1 15 5 7 1	2 6 1 1 2 15 3

Sample Explanation

প্রথম টেস্ট কেস:

$F(2, 2) = 2$, তাই $F(2, 2)$-কে যেন $5^Z$ নিঃশেষে ভাগ করে এমন $Z$-এর সবচেয়ে বড় মান $Z = 0$।

সূতরাং, $\displaystyle \frac{F(2, 2)}{5^0} = 2$ এবং উত্তর 2।

দ্বিতীয় টেস্ট কেস:

$F(3, 2) = 6$, তাই $F(3, 2)$-কে যেন $7^Z$ নিঃশেষে ভাগ করে এমন $Z$-এর সবচেয়ে বড় মান $Z = 0$।

সূতরাং, $\displaystyle \frac{F(3, 2)}{7^0} = 6$ এবং উত্তর 6।

তৃতীয় টেস্ট কেস:

$F(3, 2) = 6$, তাই $F(3, 2)$-কে যেন $5^Z$ নিঃশেষে ভাগ করে এমন $Z$-এর সবচেয়ে বড় মান $Z = 0$।

সূতরাং, $\displaystyle \frac{F(3, 2)}{5^0} = 6$। এখানে, $P^Q = 5^1 = 5$।

$\displaystyle \frac{F(3, 2)}{5^0} \equiv 1 \pmod {5^1}$, তাই উত্তর 1।

চতুর্থ টেস্ট কেস:

$F(3, 2) = 6$, তাই $F(3, 2)$-কে যেন $2^Z$ নিঃশেষে ভাগ করে এমন $Z$-এর সবচেয়ে বড় মান $Z = 1$।

সূতরাং, $\displaystyle \frac{F(3, 2)}{2^1} = 3$। এখানে, $P^Q = 2^1 = 2$।

$\displaystyle \frac{F(3, 2)}{2^1} \equiv 1 \pmod {2^1}$, তাই উত্তর 1।

Notes

কম্পিউটার সায়েন্সে, ট্রি একটি বহুল ব্যবহৃত অ্যাবস্ট্রাক্ট ডেটা টাইপ।

একটি ট্রি ডেটা স্ট্রাকচারকে নোডের সংগ্রহ (যা রুট নোড থেকে শুরু হয়) হিসাবে পুনরাবৃত্তভাবে (রিকার্সিভলি) সংজ্ঞায়িত করা যেতে পারে, যেখানে প্রতিটি নোড একটি ডেটা স্ট্রাকচার যার মধ্যে একটা ভ্যালু থাকে এবং চাইল্ড নোডগুলোর রেফারেন্সের তালিকা থাকে; সাথে আরেকটা রুল থাকে যে সব রেফারেন্স স্বতন্ত্র (ইউনিক) এবং কোনটি রুট নোডকে পয়েন্ট করে না।