+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- کیان و دوستان برای تعطیلات به شمال رفته‌اند. در راه برای کباب درست کردن کنار برکه‌ای توقف می‌کنند. در آنجا تعداد زیادی نیلوفر آبی می‌بینند و تعدادی قورباغه که بر روی آن‌ها می‌پرند. ترتیب منظم نیلوفر‌های آبی نظر کیان را جلب کرد. زیبایی برکه در آن بود که $n$ نیلوفر آبی در یک ردیف و با فاصله‌ی ۱ متر از یک‌دیگر قرار گرفته بودند. کیان با کمی دقت بیشتر متوجه شد که اگر قورباغه‌ای از نیلوفر آبی‌ $a$ به نیلوفر آبی $b$ بپرد، نیلوفر آبی $a$ به زیر آب می‌رود و قورباغه‌ی دیگری نمی‌تواند روی آن بپرد. کمیته ملی برای مراسم افتتاحیه المپیاد جهانی ۲۰۱۷، از کیان و ملک درخواست ایده‌ای جدید کرده است. برای همین آن‌ها تصمیم می‌گیرند برکه‌ای مصنوعی با $n$ نیلوفر آبی با فاصله‌ی $1$ متر آماده کنند. نیلوفر‌ها را از چپ به راست با $1$ تا $n$ شماره‌گذاری شده‌اند. آن‌ها قصد دارند که $k$ قورباغه را به گونه‌ای تربیت کنند که به صورت زیر رقص‌قورباغه‌ای انجام دهند: + در ابتدا $k$ قورباغه بر روی $k$ نیلوفر‌آبی نخست بنشینند. + برای زیبایی بیشتر تصمیم گرفته‌اند قورباغه‌ها تنها به سمت راست بپرند. + در انتها $k$ قورباغه روی $k$ نیلوفرآبی پایانی بنشینند. + هر نیلوفر آبی، در دنباله‌ی حرکت یک قورباغه آمده باشد. توجه کنید که: + در هیچ زمانی دو قورباغه بر روی یک نیلوفر آبی قرار نمی‌گیرند. + قورباغه‌ها با توجه به توان کم آن‌ها حداکثر می‌توانند $p$ متر بپرند. + نیلوفر‌های آبی توان زیادی ندارند و بعد از پرش هر قورباغه زیر آب می‌روند. ملک که به دنبال سؤال برای امتحان‌ها است با دیدن این برنامه ناگهان سؤالی طرح می‌کند. سؤال به این صورت است که با شرایط بالا رقص قورباغه‌ای به چند روش متفاوت ممکن است اجرا شود. از آنجا که ملک سخت درگیر آماده سازی آزمون‌ها هست از شما خواسته است برنامه‌ای بنویسید که تعداد روش‌های رقص‌قورباغه‌ای را بشمارد. از آنجا که ممکن است جواب بزرگ باشد، حاصل آن را به پیمانه‌ی $10^9 + 7$ حساب کنید. دو روش متفاوت است اگر و تنها اگر قور باغه‌ای وجود داشته باشد که بر روی دنباله‌ی متفاوتی از نیلوفر‌های آبی قرار گرفته‌باشد. # ورودی در تنها خط ورودی، به ترتیب سه عدد طبیعی $n$، تعداد نیلوفر‌های آبی، $k$ ، تعداد قورباغه‌ها و $p$، حداکثر پرش یک قورباغه، آمده است. $$ 1 \le n \le 10^{18}$$ $$1 \le k \le p \le min(10,n)$$ # خروجی در تنها خط خروجی، تعداد روش‌ها را به پیمانه‌ی $10^9 + 7$ چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۱۱ | $ k , p \le 6$ و $ n \le 15$ | | ۲ | ۱۳ | $ k , p \le 6$ و $ n \le 1\ 000$ | | ۳ | ۱۹ | $ k , p \le 6$ | | ۴ | ۳۶ | $ k , p \le 9$ | | ۵ | ۲۱ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 3 2 2 ``` ## خروجی نمونه ۱ ``` 1 ``` ## ورودی نمونه ۲ ``` 4 2 3 ``` ## خروجی نمونه ۲ ``` 2 ``` ## ورودی نمونه ۳ ``` 14 3 6 ``` ## خروجی نمونه ۳ ``` 14020 ```