শিশুশ্রম একটি বৈশ্বিক সমস্যা। তুমি একজন সমস্যা সমাধানকারী। তাই তোমাকে এই সুবিধাবঞ্চিত শিশুদের সম্পর্কে ধারণা রাখতে হবে যারা শিক্ষা সহ অন্যান্য মৌলিক অধিকার পায় না। এই শিশুরা কাজে যেতে বাধ্য হয়। এটি একটি বাস্তব সমস্যা যা তোমাকে অদূর ভবিষ্যতে সমাধান করতে হবে যখন তুমি একজন বড় প্রোগ্রামার হবে এবং সমাজের জন্য কিছু করতে পারবে।
এখন আমি তোমাদের দীপ্তর গল্প বলছি। দীপ্ত তার বাড়ি থেকে দূরে একটি কারখানায় কাজ করে। তার অসুস্থ মা এবং ছোট বোনের দেখাশোনা করতে হয়। দীপ্ত যে শহরটিতে থাকে সেটিকে একটি $N\times M$ আকারের ছক দিয়ে দেখানো যায়। ছকের প্রতিটি বর্গে একটি করে ইংরেজী অক্ষর থাকে। দীপ্ত $\mathbf{(1, 1)}$ বর্গে থাকে এবং $\mathbf{(N, M)}$ বর্গের কারখানায় কাজ করতে যায়। সে $(x, y)$ বর্গ থেকে শুধুমাত্র $(x+1, y)$ অথবা $(x, y+1)$ বর্গে যেতে পারে। এভাবে $(1, 1)$ থেকে $(N, M)$ বর্গে অনেকগুলো ভিন্ন ভিন্ন পথে যাওয়া যায়।
দীপ্ত বাসা থেকে কর্মস্থলে যাওয়ার সময় ভালো পথ দিয়ে যেতে পছন্দ করে।
ভালো পথ হল সে পথ যে পথে থাকা বর্গগুলো থেকে ক্যারেক্টারগুলোকে নিয়ে যেকোনভাবে সাজিয়ে একটি প্যালিনড্রোম বানানো সম্ভব।প্যালিনড্রোম হল এমন কিছু বিশেষ শব্দ যা যার আরম্ভ বা শেষ দুদিক থেকেই পড়লে একই থাকে যেমন madam, racecar ।
তোমার মতো প্রোগ্রামাররা দীপ্তর মতো বাচ্চাদের জন্য স্কুল প্রতিষ্ঠা করতে চায়। তাই তারা জানতে চায় $(a, b)$ বর্গে একটি স্কুল প্রতিষ্ঠা করা হলে এমন কতগুলো ভালো পথ পাওয়া যাবে যেন পথে এই স্কুলটি থাকে।
ভালো করে বুঝে নেওয়ার জন্য নীচের ছবিটি লক্ষ্য কর। এই ম্যাপে দীপ্তর শহরটিকে দেখানো হয়েছে একটি ছক দ্বারা । ছকটির আকার $N\times M$ যেখানে $N = 3$ এবং $M = 4$
দীপ্ত থাকে $(1, 1)$ ঘরে এবং কাজ করতে যায় $(3, 4)$ ঘরে।
এখানে ভালো পথের উদাহরণ হল $(1,1) → (1,2) → (2,2) → (3,2) → (3,3) → (3,4)$ । এই পথে সে যে অক্ষরগুলো সংগ্রহ করতে পারবে সেগুলো দিয়ে একটি শব্দ বানানো যায় $\mathbf{''abbaaa''}$ । এবার শব্দটির অক্ষরগুলোকে ভিন্নভাবে সাজিয়ে পাওয়া যায় $\mathbf{''aabbaa''}$ । এটি একটি প্যালিনড্রোম । সুতরাং এটি একটি ভালো পথ।
যদি তুমি $(3, 3)$ ঘরে একটি স্কুল প্রতিষ্ঠা করো তাহলে এমন দুইটি ভালো পথ পাওয়া সম্ভব যেন স্কুলটি ঐ পথগুলোতে থাকে। ছবিতে লাল রঙ দিয়ে একটি ভালো পথ দেখান হয়েছে , নীল রঙ দিয়ে অন্যটি।
তুমি এই প্রকল্পের একজন স্বেচ্ছাসেবী। তোমার কাজ হচ্ছে কম্পিউটার প্রোগ্রাম লিখে এই হিসাবগুলোকে সহজ করে দেওয়া। এমন একটি প্রোগ্রাম লিখ যেখানে তোমাকে শহরের ম্যাপটা বলে দেওয়া হবে এবং কোন ঘরে কোন অক্ষর আছে সেটাও বলে দেওয়া হবে। তোমার প্রোগ্রামটি ম্যাপের প্রতিটা ঘরের জন্য গণনা করবে যে কতগুলো পথ এই ঘরে থাকা স্কুলটি হয়ে যাবে। যেহেতু উত্তরগুলো অনেক বড় সংখ্যা হতে পারে তাই তোমরা আসল উত্তরকে $\mathbf{1000000007}$ দিয়ে ভাগ করে ভাগশেষটি প্রিন্ট করবে।
Input
ইনপুটের একদম প্রথম লাইনে টেস্ট কেসের সংখ্যা $T$ দেওয়া হবে । এরপর প্রতি টেস্ট কেস শুরু হবে দুইটি সংখ্যা $N$ এবং $M$ দিয়ে।
এরপরের $N$ টি লাইনের প্রত্যেকটিতে একটি করে স্ট্রিং দেওয়া হবে। $i^{তম}$ লাইনের $j^{তম }$ ক্যারেক্টারটি হল $(i,j)$ বর্গে থাকা অক্ষরটি।
$\mathbf{Constraints}$
সাবটাস্ক #১ (১০ পয়েন্টের জন্য):$1 \leq T \leq 100$$N = 1$$2 \leq M \leq 10000$
সাবটাস্ক #২ (৩০ পয়েন্টের জন্য):$1 \leq T \leq 100$$N = 2$$2 \leq M \leq 10000$
সাবটাস্ক #৩ (৬০ পয়েন্টের জন্য):$1 \leq T \leq 10$$3 \leq N \leq 40$$3 \leq M \leq 40$
এটা নিশ্চিত যে ছকের প্রতিটি বর্গে থাকা অক্ষরগুলো প্রথম ১০ টি ছোট হাতের ইংরেজি বর্ণমালার মধ্যেই থাকবে।
Output
প্রতিটি টেস্ট কেসের জন্য প্রথমে প্রিন্ট করঃ ''Case x:'' কোটেশন মার্ক ছাড়া, যেখানে x হলো কত নম্বর টেস্ট কেসে এখন আছো সেটা।
এরপর $N$ টি পৃথক লাইন প্রিন্ট করতে হবে। প্রতিটি লাইনে $M$ টি করে পূর্ণসংখ্যা প্রিন্ট করতে হবে। একটি লাইনে প্রিন্ট করা পরপর দুইটি সংখ্যার মাঝে একটি স্পেস থাকবে। $i^{তম}$ লাইনের $j^{তম }$ পূর্ণসংখ্যাটিই $(i,j)$ বর্গের জন্য নির্ণেয় উত্তর। যেহেতু উত্তরগুলো অনেক বড় সংখ্যা হতে পারে তাই তোমরা আসল উত্তরকে $\mathbf{1000000007}$ দিয়ে ভাগ করে ভাগশেষটি প্রিন্ট করবে।
Samples
| Input | Output |
|---|---|
1 1 4 aaaa | Case 1: 1 1 1 1 |
| Input | Output |
|---|---|
1 2 5 aaaaa aaaaa | Case 1: 5 4 3 2 1 1 2 3 4 5 |
| Input | Output |
|---|---|
1 3 4 aaaa aaaa aaaa | Case 1: 10 6 3 1 4 6 6 4 1 3 6 10 |
