יום אחד, 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