রাজকুমারী পিচ আবারো অপহরণ হয়ে গিয়েছে (সত্যি, আবার?)! সে তার বাগানে হাঁটছিল, এমন সময় হুট করে একটি পোর্টাল খুলে তার ভিতর থেকে কিছু ব্রাউজার দ্বারা ভাড়াটে মহাশূন্য দস্যু হাজির হল। পোর্টালটি ব্যবহার করে তারা রাজকুমারীকে একটি দুর্গতে বহন করে নিয়ে গেল, যেটি একটি মহাশূন্যযান এর ভিতরে অবস্থিত।

সব বারের মত, উদ্ধার করার দায়িত্ব পরল মারিও এর ঘাড়ে। কোন এক কারণে, রাজ্যের নিজস্ব কোন যোদ্ধা নেই এবং প্রত্যেকবার একটি মিস্ত্রি এর উপর ভরসা করতে হয় তাদের। কে জানে, স্নান ঘরের ঝরনা ভেঙ্গে গেলে তারা কাদের কে ডাকে।

যায় হোক, অনেক গুলি লেভেল পার করে মারিও শেষ লেভেল এ আসতে পেরেছে। শেষ লেভেলটি একটি N dimension জগত এ হচ্ছে। মারিও একটি মহাশূন্যযান এর ভিতরে এবং তার আর রাজকুমারীর মাঝে শত্রু এর সাগর।

মারিও সব অক্ষ রেখা এর মাঝে উদিত হয় যেখানে সব স্থানাঙ্ক শুন্য। শত্রুরা তাকে চারিদিক থেকে ঘিরে আছে। সরলতার খাতিরে ধরে নেওয়া যাক যে মহাশূন্যযান গুলো একটি বিন্দুর মত এবং তাদের স্থানাঙ্ক গুলো পূর্ণসংখ্যা। তার মানে, N dimension-এ যদি স্থানাঙ্ক হবে এরকমঃ (a1,a2,a3...aN) যেখানে {a1,a2,a3...aN} সব পূর্ণসংখ্যা। শুধুমাত্র মধ্যবিন্দু ছাড়া যেখানে মারিও উদিত হয়েছে, বাকি সব পূর্ণসংখ্যার স্থানাঙ্ক গুলোতে একটি করে শত্রু আছে।

এখন, রাজকুমারী কোথায় হতে পারে? এতগুলো শত্রুদের মহাযান আছে। মারিও-এর হটাৎ রাজার দুটি কথা মনে পরে গেল।

১) রাজকুমারীকে এমন এক বাহনে রাখা হয়েছে যার স্থানাঙ্ক-এর মাঝে কোন ঋণাত্মক সংখ্যা থাকবে নাহ। অর্থাৎ, {a1,a2,a3...aN} >= 0।

২) রাজকুমারীকে এমন এক বাহনে রাখা হয়েছে যার মধ্যবিন্দু থেকে ট্যাক্সিক্যাব দূরত্ব K-এর থেকে বেশি নাহ। যদি দুটি বিন্দুর স্থানাঙ্ক হয় {a1,a2,a3...aN} এবং {b1,b2,b3...bN}, তাহলে তাদের মধ্যে ট্যাক্সিক্যাব দূরত্ব হল |a1-b1|+|a2-b2|+|a3-b3|...+|aN-bN|।

এখন তোমাকে N এবং K দেওয়া হল, তোমাকে বলতে হবে কতগুলো শত্রুকে মারিও-এর হারাতে হবে রাজকুমারীকে বাঁচানোর জন্যে? উত্তরটি অনেক বড় হতে পারে, কিন্তু ভাগ্য ভাল যে মারিওকে যদি উত্তরটি (10^9+7) দিয়ে mod করে দেই, সে তারপরও খুশি হবে।

Princess Peach has been kidnapped again (seriously, again?)! She was taking a stroll in her garden, when suddenly a portal opened and some space pirates hired by Browser appeared. Using the portal they transferred Princess to a Castle built inside a spacecraft, in some parallel dimension.

As usual, it is Mario’s responsibility to rescue her. For some reason, the Kingdom doesn’t have any Knights and need to rely on the plumber every time. I wonder who gets called when there is a broken toilet in there kingdom?

Anyways, after a long journey through many levels ( or short journey using shortcuts between levels ) Mario has managed to come to the last level. The last level is happening inside a N dimensional world. He is inside a spacecraft and between him and Princess lies a sea of enemies.

Mario spawns at the center of all axis, with all coordinates 0. The enemies are surrounding him from every direction. For simplicity of the problem, the spacecrafts are assumed to be points and have only integer coordinates. That is, a coordinate in N dimension will be of following form: (a1,a2,a3...aN) where {a1,a2,a3...aN} are all integers. Except for the center point where Mario has spawned, every other integer point has a single enemy vessel at the location.

Now, where can the Princess be? There are so many enemy vessels? Mario suddenly remembers the two hints given to him by the King.

1. Princess is held captive in a vessel which only has non-negative integers in its coordinate. That is, {a1,a2,a3...aN} >= 0.

2. Princess is held captive in a vessel which has taxicab distance at most K from the center point. If two points have coordinate {a1,a2,a3...aN} and {b1,b2,b3...bN}, then the taxicab distance between them equals to |a1-b1|+|a2-b2|+|a3-b3|...+|aN-bN|.

Now, given N and K, how many enemy vessel does Mario need to defeat to find Princess? The answer maybe too big, but luckily Mario will be happy if you just tell him the result modulo (10^9+7).