کیان و دوستان برای تعطیلات به شمال رفته‌اند. در راه برای کباب درست کردن کنار برکه‌ای توقف می‌کنند. در آنجا تعداد زیادی نیلوفر آبی می‌بینند و تعدادی قورباغه که بر روی آن‌ها می‌پرند. ترتیب منظم نیلوفر‌های آبی نظر کیان را جلب کرد. زیبایی برکه در آن بود که $n$ نیلوفر آبی در یک ردیف و با فاصله‌ی ۱ متر از یک‌دیگر قرار گرفته بودند. کیان با کمی دقت بیشتر متوجه شد که اگر قورباغه‌ای از نیلوفر آبی‌ $a$ به نیلوفر آبی $b$ بپرد، نیلوفر آبی $a$ به زیر آب می‌رود و قورباغه‌ی دیگری نمی‌تواند روی آن بپرد.

کمیته ملی برای مراسم افتتاحیه المپیاد جهانی ۲۰۱۷، از کیان و ملک درخواست ایده‌ای جدید کرده است. برای همین آن‌ها تصمیم می‌گیرند برکه‌ای مصنوعی با $n$ نیلوفر آبی با فاصله‌ی $1$ متر آماده کنند. نیلوفر‌ها را از چپ به راست با $1$ تا $n$ شماره‌گذاری شده‌اند. آن‌ها قصد دارند که $k$‌ قورباغه را به گونه‌ای تربیت کنند که به صورت زیر رقص‌قورباغه‌ای انجام دهند:

• در ابتدا $k$ قورباغه بر روی $k$ نیلوفر‌آبی نخست بنشینند.
• برای زیبایی بیشتر تصمیم گرفته‌اند قورباغه‌ها تنها به سمت راست بپرند.
• در انتها $k$ قورباغه روی $k$ نیلوفرآبی پایانی بنشینند.
• هر نیلوفر آبی، در دنباله‌ی حرکت یک قورباغه آمده باشد.

توجه کنید که:

• در هیچ زمانی دو قورباغه بر روی یک نیلوفر آبی قرار نمی‌گیرند.
• قورباغه‌ها با توجه به توان کم آن‌ها حداکثر می‌توانند $p$ متر بپرند.
• نیلوفر‌های آبی توان زیادی ندارند و بعد از پرش هر قورباغه زیر آب می‌روند.

ملک که به دنبال سؤال برای امتحان‌ها است با دیدن این برنامه ناگهان سؤالی طرح می‌کند. سؤال به این صورت است که با شرایط بالا رقص قورباغه‌ای به چند روش متفاوت ممکن است اجرا شود. از آنجا که ملک سخت درگیر آماده سازی آزمون‌ها هست از شما خواسته است برنامه‌ای بنویسید که تعداد روش‌های رقص‌قورباغه‌ای را بشمارد. از آنجا که ممکن است جواب بزرگ باشد، حاصل آن را به پیمانه‌ی $10^9 + 7$ حساب کنید.

دو روش متفاوت است اگر و تنها اگر قور باغه‌ای وجود داشته باشد که بر روی دنباله‌ی متفاوتی از نیلوفر‌های آبی قرار گرفته‌باشد.

در تنها خط ورودی، به ترتیب سه عدد طبیعی $n$، تعداد نیلوفر‌های آبی، $k$، تعداد قورباغه‌ها و $p$، حداکثر پرش یک قورباغه، آمده است.

در تنها خط خروجی، تعداد روش‌ها را به پیمانه‌ی $10 ^ 9 + 7$ چاپ کنید.

• زیرمسئله اول (۱۱ نمره): $n\leq 15$, $k,p\leq 6$
• زیرمسئله دوم (۱۳ نمره): $n\leq 1000$, $k,p \leq 6$
• زیرمسئله سوم (۱۹ نمره):$k,p\leq 6$
• زیرمسئله چهارم (۳۶ نمره):$k,p\leq 9$
• زیرمسئله پنجم (۲۱ نمره): بدون محدودیت اضافی

• $ 1 \leq n \leq 10^{18} $
• $ 1 \leq k \leq p \leq min\{10,n\} $

در ورودی نمونه‌ی اول، برای پرش اول تنها دو حالت زیر را داریم:

• قورباغه‌ی دوم بر روی نیلوفر سوم بپرد. در این صورت بعد از پرش قورباغه‌‌ی دوم، نیلوفر دوم به زیر آب می‌رود. در این صورت قورباغه‌ی اول روی نیلوفر یک و قورباغه‌ی دوم روی نیلوفر سوم است. در این‌صورت هیچ کدام از قورباغه‌ها قابلیت پرش ندارند و بنابراین نمی‌توانیم به وضعیتی برسیم که قوباغه‌ها در دو نیلوفر آبی آخر باشند.

• قورباغه‌ی اول بر روی نیلوفر سوم می‌پرد. در این صورت به یک وضعیت مجاز می‌رسیم.

بنابراین تعداد روش‌های رقص قورباغه‌ای برابر یک است.

• سوال بعد