"Whosoever holds this hammer, if he be worthy, shall possess the power of Thor."
এই বার্তাটি Mjolnir হাতুড়িটির সাথে নিয়ে যাওয়া হয়েছিলো। বজ্রদেবতা মত, থর ঝড়ের উপাদানগুলোকে (বজ্রপাত, বৃষ্টি, বাতাস, তুষার) ডেকে আনতে পারে এবং এই ক্ষমতাকে জাহির করার জন্য সে হাতুড়িটিকে একটি সরঞ্জাম হিসেবে ব্যবহার করে। তবে Mjolnir হাতুড়িটি হেলার (থরের বোন) দ্বারা ধ্বংস হয়ে গিয়েছিলো। থরের কাছে এখন Strombreaker নামের একটি কুঠার আছে। এটা নিদাভেলির উরু দিয়ে তৈরি করা হয়েছিল। এইত্রি (থরের এক বন্ধু) দাবি করেছেন যে অস্ত্রটিকে আসগার্ডের ইতিহাসের সবচেয়ে শক্তিশালী অস্ত্র হিসেবে বোঝানো হয়েছিল।
থানোস (দুর্দান্ত খলনায়ক) আসছে। তার একটি N সংখ্যক বিশাল সেনাবাহিনী রয়েছে। প্রত্যেকটা শত্রুর আলাদা ধরণের শক্তি আছে। তারা সবাই একটি লাইনে সাজানো আছে। থর তাদের সবাইকে পরাজিত করার সিদ্ধান্ত নিয়েছে এবং সে শত্রুদের উপর বিদ্যুতের সাহায্যে আক্রমণ করবে। প্রতিটি আক্রমণে থর শত্রুর মোট X শক্তি হ্রাস করতে পারে। থর K এর বেশি বার আক্রমণ করতে চায় না।
তাই, থর N জন শত্রুকে সর্বোচ্চ K ভাগে ভাগ করতে চায়, যাতে প্রতি ভাগের মোট শক্তি X কে অতিক্রম না করে। যেহেতু শত্রুরা একটি মাত্র লাইনে দাঁড়িয়ে আছে, তাকে **ধারাবাহিক **ভাবে ভাগ করতে হবে। কোন ভাগ খালি থাকতে পারবে না।
প্রথম লাইনে ৩ টি পূর্ণসংখ্যা থাকবে - N, K এবং X.
দ্বিতীয় লাইনে N সংখ্যক পূর্ণসংখ্যা a1, a2, ..... an থাকবে যা থানোসের সেনাবাহিনীর শক্তি বুঝায়।
ai, i তম শত্রুর শক্তি নির্দেশ করে।
Constraint:
থর কতভাবে তার শত্রুকে সর্বোচ্চ K ভাগে ভাগ করতে পারে যাতে কোন ভাগের শক্তি X কে অতিক্রম না করে সেটি প্রিন্ট করতে হবে। তোমার উত্তরটি অনেক বড় হতে পারে। একে 109 + 7 এর ভাগশেষ আকারে প্রিন্ট করতে হবে।
Input | Output |
---|---|
3 3 6 1 2 3 | 4 |
Input | Output |
---|---|
5 3 3 1 2 3 2 1 | 1 |