ל־Bessie יש רצועת בד ציור באורך $N$ יחידות ($1 \leq N \leq 10^6$), והיא רוצה לצייר עליה, אך לא הצליחה להשיג מכחולים. במקומם יש לה $M$ חותמות גומי בצבעים שונים ($1 \leq M \leq 10^6$), כל אחת ברוחב $K$ יחידות ($1 \leq K \leq 10^6$). נדהמת מהאפשרויות, היא רוצה לדעת בדיוק כמה ציורים שונים תוכל ליצור בהחתמה בסדר כלשהו.

יש ליישר חותמת עם בדיוק $K$ יחידות סמוכות בבד. היא אינה יכולה לחרוג מהקצוות או לכסות חלקי יחידות. היא צובעת את $K$ היחידות המכוסות בצבע שלה. בכל חותמת ניתן להשתמש פעמים רבות, פעם אחת או כלל לא. אך כש־Bessie מסיימת, כל יחידה חייבת להיות צבועה לפחות פעם אחת.

עזרו ל־Bessie למצוא את מספר הציורים השונים מודולו $10^9 + 7$. ציורים זהים במראה שנוצרו ברצפי החתמה שונים נחשבים לאותו ציור.

קלט

השורה היחידה מכילה שלושה שלמים $N$, $M$ ו־$K$. מובטח $K \leq N$.

פלט

שלם יחיד: מספר הציורים האפשריים מודולו $10^9 + 7$.

דוגמאות

קלט 1

3 2 2

פלט 1

6

הערה

אם צבעי שתי החותמות הם A ו־B, הציורים האפשריים הם AAA, AAB, ABB, BAA, BBA ו־BBB.

תתי־משימות

בלפחות $75\%$ ממקרי הקלט מתקיים $N,K \leq 10^3$.

מחבר הבעיה: Dhruv Rohatgi