+ محدودیت زمان: ۰٫۵ ثانیه + محدودیت حافظه: ۵۰ مگابایت + محدودیت اعداد: تمامی اعداد ورودی و خروجی از $10^{18}$ کوچک‌ترند. ---------- پس از انتخاب چارلی به عنوان جانشین اصلح ویلی‌وانکا طی جریاناتی (به متن اصلی کتاب مراجعه کنید یا [کتاب را بخرید](https://www.amazon.com/Charlie-Chocolate-Factory-Roald-Dahl/dp/0142410314))، ویلی‌وانکا برای انتصاب او تصمیم به انجام آخرین تست خود گرفت. او به چارلی یک مسئله‌ی المپیادی داد تا حل کند:  جایگشت $n$ تایی $A$ به دنباله‌ای دارای $n$ عدد مانند $<a_1, a_2, ..., a_n>$ گفته می‌شود که هریک از اعداد ۱ تا $n$ دقیقا یک بار در آن ظاهر شده‌باشند. حال جایگشت $n$ تایی $X$ را در نظر بگیرید. جایگشت $Y$ را این‌گونه تعریف می‌کنیم: + داریم: $y_1 = 1$ + به ازای هر $i$ بین ۲ تا $n$ اگر هیچ‌یک از اعداد $y_1$ تا $y_{i-1}$ در $Y$ برابر $x_{i-1}$ نبود، آن‌گاه $y_i = x_{i-1}$. در غیر این‌صورت $y_i$ را برابر کوچک‌ترین عددی از ۱ تا $n$ می‌گذاریم که برابر هیچ‌یک از اعداد $y_1$ تا $y_{i-1}$ در $Y$ نباشد. در این صورت جایگشت $Y$ را **تصویر**ی از جایگشت $X$ می‌نامیم و می‌گوییم: $f(X) = Y$. حال $g(Y)$ را تعداد جواب‌های معادله‌ی $f(X) = Y$ تعریف می‌کنیم.به عبارت دیگر $g(Y)$ تعداد تمام جایگشت‌های $n$ تایی‌ای مانند $X$ است که $f(X) = Y$. ویلی‌وانکا به‌عنوان آخرین چالش چارلی به او دو عدد $L$ و $R$ را می‌دهد و چارلی باید تعداد تمام جایگشت‌های $n$ تایی از اعداد ۱ تا $n$ مانند $A$ که $L \leq g(A) \leq R$ باشد را به او پاسخ دهد. از آن‌جا که این عدد ممکن است خیلی بزرگ باشد، باقی‌مانده‌ی تقسیم آن بر $10^9 + 7$ را خروجی دهید. # ورودی در سطر اول عدد $n \leq 2 \times 10^5$ ‫‫—‬ اندازه‌ی جایگشت‌ها آمده‌است. در سطر بعدی دو عدد $L, R \leq 10^{18}$ آمده‌است. # خروجی باقی‌مانده‌ی جواب مسئله بر $10^9+7$ را چاپ کنید. ### نمونه‌ی ورودی 3 0 10 ### نمونه‌ی خروجی 6 ### نمونه‌ی ورودی 3 2 1 ### نمونه‌ی خروجی 0 ### نمونه‌ی ورودی 7 8 14 ### نمونه‌ی خروجی 225