في يوم من الأيام، حصل JOI-kun على آلة زمن. وقرر الذهاب إلى اليابان في القرن التاسع. وهناك التقى Kukai، أحد أشهر الرهبان في اليابان آنذاك. كان الراهب يريد ابتكار طريقة جديدة للتدريب.
يجري تدريبه على النحو الآتي:
- يقرأ Kukai نصًا دينيًا يتكون من $N$ جملة. هذه الجمل مرتبة، وعليه قراءتها بالترتيب.
- تحمل كل جملة عددًا صحيحًا واحدًا بين $1$ و$N$، شاملًا الطرفين. ولا تحمل جملتان مختلفتان العدد نفسه.
- عليه قراءة الجملة التي تحمل العدد الصحيح $i$ ($1\le i\le N$) في الفترة رقم $i$ من الفترات الزمنية المتساوية وعددها $N$ التي يُقسَّم إليها اليوم. كل جملة قصيرة بما يكفي ليتمكن دائمًا من قراءتها خلال فترة واحدة.
يريد Kukai قراءة النص الديني بأكمله في أسرع وقت ممكن. لكن عدد الأيام اللازمة لإنهائه يعتمد على الأعداد المكتوبة على الجمل. طلب Kukai من JOI-kun حساب عدد الطرق الممكنة لتوزيع الأعداد على الجمل التي تجعل Kukai يحتاج إلى $K$ يومًا بالضبط لإنهاء القراءة إذا قرأ على النحو الأمثل.
المهمة
بمعرفة عدد الجمل $N$ وعدد صحيح $K$، احسب عدد الطرق الممكنة لتوزيع الأعداد على الجمل التي تجعل Kukai يحتاج إلى $K$ يومًا بالضبط لإنهاء القراءة إذا قرأ على النحو الأمثل، بترديد $1\,000\,000\,007$.
الإدخال
اقرأ البيانات الآتية من الإدخال القياسي.
- يحتوي السطر الأول من الإدخال على $N$ و$K$، تفصل بينهما مسافة واحدة.
الإخراج
اطبع عدد الطرق الممكنة لتوزيع الأعداد على الجمل التي تجعل Kukai يحتاج إلى $K$ يومًا بالضبط لإنهاء القراءة إذا قرأ على النحو الأمثل، بترديد $1\,000\,000\,007$.
القيود
تستوفي جميع بيانات الإدخال الشروط الآتية.
- $1\le N\le 100\,000$.
- $1\le K\le N$.
المهام الفرعية
توجد 4 مهام فرعية. وفيما يأتي درجات كل مهمة فرعية وقيودها الإضافية:
المهمة الفرعية 1 [4 درجات]
- $N\le 10$.
المهمة الفرعية 2 [20 درجة]
- $N\le 300$.
المهمة الفرعية 3 [25 درجة]
- $N\le 3\,000$.
المهمة الفرعية 4 [51 درجة]
لا توجد قيود إضافية.
أمثلة
الإدخال 1
3 2
الإخراج 1
4
ملاحظة
توجد 4 طرق ممكنة لتوزيع الأعداد على الجمل تجعله يحتاج إلى يومين لإنهاء القراءة.
- تحمل الجملة الأولى العدد $1$، والتالية العدد $3$، والأخيرة العدد $2$. يقرأ الجملتين الأوليين (اللتين تحملان العددين $1$ و$3$ على الترتيب) في اليوم الأول، والجملة الأخيرة (التي تحمل العدد $2$) في اليوم الثاني.
- تحمل الجملة الأولى العدد $2$، والتالية العدد $1$، والأخيرة العدد $3$.
- تحمل الجملة الأولى العدد $2$، والتالية العدد $3$، والأخيرة العدد $1$.
- تحمل الجملة الأولى العدد $3$، والتالية العدد $1$، والأخيرة العدد $2$.
الإدخال 2
10 5
الإخراج 2
1310354