Limits 4s, 512 MB

হিমি খুব ভালো মেয়ে তবে পড়াশুনায় খুব অলস ও অমনোযোগী। তাই তার শিক্ষক তাকে একটি শাস্তি দেয়ার সিদ্ধান্ত নিয়েছে। প্রতিবার হিমি আলসেমিতে বাড়ির কাজগুলি ফাকি দিলে তাকে নিম্নলিখিত কাজটি করতে হবে: -

হিমিকে ঠিক $N$ টি স্ট্রিং তৈরি করতে হবে, প্রত্যেকটিতে $M$ টি অক্ষর থাকবে। বৈধ বর্ণমালাগুলো হল 'a', 'b', 'c' (সবগুলো ছোট হাতের ইংরেজী অক্ষর) বা যদি কোন অক্ষর খালি ছেড়ে রাখতে চায় তবে সে ’#’ ব্যবহার করতে পারে। অবশেষে, তাকে তার শিক্ষককে বলতে হবে যে সে কতভাবে এই স্ট্রিংগুলো তৈরি করতে পারে।

সব ঠিক আছে কিন্তু একটি শর্ত আছে, প্রতিটি পাশাপাশি স্ট্রিং অবশ্যই প্রদত্ত নিয়মটি অনুসরণ করতে হবে: -

  • ধরা যাক i তম স্ট্রিংটি $X$ এবং (i + 1) তম স্ট্রিং Y এবং অক্ষরের ঘরগুলোকে j দ্বারা চিহ্নিত করা যায়। এরপর, $X$ এর কোন অক্ষর যদি $X[j]$ হয় তাহলে $Y[j - 1]$ এবং $Y[j + 1]$ কোনটাই $X[j]$ এর সাথে মেলা যাবেনা। যদি j - 1 বা j + 1 সীমার বাইরে চলে যায় তবে সেই শর্তগুলো প্রযোজ্য হবে না। কিন্তু হিমি চাইলে $Y[j - 1]$ এবং/অথবা $Y[j + 1]$ খালি (’#’) রাখতে পারে এবং এক্ষেত্রেও শর্তগুলি প্রযোজ্য হবে না।

এছাড়াও, কোনও স্ট্রিংয়ে টির বেশি ভিন্ন-ভিন্ন বর্ণমালা থাকতে পারবে না। যেমনঃ "aaba" একটি সঠিক স্ট্রিং কিন্তু "aabc" এই নিয়ম বহির্ভূত।

হিমি অলস হতে পারে তবে সে খুবই বুদ্ধিমতী। তুমি হিমির জানা সেরা প্রোগ্রামার এবং সে জানে তুমি তার এই ক্লান্তিকর কাজটি একটি প্রোগ্রাম লিখে সহজ করে দিতে পারো।

তোমার স্বাচ্ছন্দ্যের জন্য, হিমি উপরে উল্লেখিত নিয়মগুলো অনুসরণ করে প্রথম স্ট্রিংটি তৈরি করে দিয়েছে। প্রথম স্ট্রিংটি(১ম লাইন) তুমি পরিবর্তন করতে পারবে না।

Input

ইনপুটের প্রথম লাইনে থাকবে $T$, যা হিমির শাস্তি সংখ্যা নির্দেশ করে। এরপরের লাইন থেকে প্রতিটি শাস্তির বর্ণনা হিসেবে দুটি পূর্ণসংখ্যা $N, M$ এবং $M$ দৈর্ঘ্যের প্রথম স্ট্রিং $S$ দেয়া থাকবে।

সীমাসমূহ

সাবটাস্ক ১ঃ (৫ পয়েন্ট)

$1 \leq T \leq 50$
$1 \leq M \leq 1$
$1 \leq N \leq 10^7$

সাবটাস্ক ২ঃ (১৫ পয়েন্ট)

$1 \leq T \leq 50$
$1 \leq M \leq 3$
$1 \leq N \leq 5$

সাবটাস্ক ৩ঃ (সর্বোচ্চ ৩০ পয়েন্ট)

$1 \leq T \leq 10$
$1 \leq M \leq 4$
$1 \leq N \leq 10^4$

সাবটাস্ক ৪ঃ (সর্বোচ্চ ৫০ পয়েন্ট)

$1 \leq T \leq 4$
$1 \leq M \leq 4$
$1 \leq N \leq 10^9$

সাবটাস্ক ৩ এবং ৪ এর ৫০% ক্ষেত্রে $M \leq 3$ থাকবে

Output

হিমির প্রতিটি শাস্তির ক্ষেত্রে তোমাকে "Case #X: Y" (উদ্ধৃতি ব্যতীত) আউটপুট দিতে হবে যেখানে $X$ হল শাস্তি-নম্বর এবং $Y$ হচ্ছে ফলাফল কে $1000000007 \, \, (10^9+7)$ দিয়ে ভাগ দেয়ার পর যে ভাগশেষ থাকে সেই সংখ্যা।

Samples

InputOutput
2
1 1 a
4 1 #
Case #1: 1
Case #2: 64
InputOutput
2
2 2 aa
2 3 aaa
Case #1: 9
Case #2: 27

Submit

Login to submit.

Statistics

80% Solution Ratio
YouKnowWhoEarliest, Jul '20
Salman.306242Fastest, 1.4s
YouKnowWhoLightest, 864 kB
Salman.306242Shortest, 3090B
Toph uses cookies. By continuing you agree to our Cookie Policy.