נתונות $n$ מחרוזות התחלתיות של אותיות לטיניות קטנות, כאשר אף מחרוזת התחלתית אינה קידומת של מחרוזת התחלתית אחרת. כעת בוחרים $k$ מן המחרוזות (כל מחרוזת לכל היותר פעם אחת) ומשרשרים אותן זו לזו. כך ניתן ליצור את מספר המחרוזות המורכבות הבא:

$$ n\times(n-1)\times(n-2)\times\ldots\times(n-k+1) $$

ממיינים בסדר אלפביתי את כל המחרוזות המורכבות שניתן לקבל בתהליך זה. נתונה מחרוזת מורכבת לבדיקה, שמובטח שהיא נמצאת ברשימה זו. מצאו את מיקומה של מחרוזת הבדיקה ברשימה הממוינת של כל המחרוזות המורכבות, מודולו $10^9+7$. המחרוזת המורכבת הראשונה ברשימה נמצאת במקום $1$.

קלט

כל קלט מורכב ממקרה בדיקה יחיד. שימו לב שהתוכנית שלכם עשויה להיות מורצת מספר פעמים על קלטים שונים. כל מקרה בדיקה מתחיל בשורה המכילה שני מספרים שלמים, תחילה $n$ ואחריו $k$ ($1\le k\le n$), כאשר $n$ הוא מספר המחרוזות ההתחלתיות, ו-$k$ הוא מספר המחרוזות ההתחלתיות שבוחרים ליצירת מחרוזות מורכבות. החסמים העליונים על $n$ ועל $k$ נקבעים על ידי המגבלות על המחרוזות שבפסקאות הבאות.

כל אחת מ-$n$ השורות הבאות מכילה מחרוזת המורכבת מאות לטינית קטנה אחת או יותר, מן האותיות a עד z. אלו הן $n$ המחרוזות ההתחלתיות. מובטח שאף אחת מהמחרוזות ההתחלתיות אינה קידומת של מחרוזת התחלתית אחרת.

לבסוף, השורה האחרונה מכילה מחרוזת נוספת, המורכבת רק מאותיות לטיניות קטנות a עד z. זוהי המחרוזת המורכבת לבדיקה, שאת מיקומה ברשימה הממוינת עליכם למצוא. מובטח שמחרוזת הבדיקה היא שרשור של $k$ מחרוזות התחלתיות שונות.

סכום האורכים של כל מחרוזות הקלט, כולל מחרוזת הבדיקה, אינו עולה על $10^6$ אותיות.

פלט

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

דוגמאות

קלט 1

5 3
a
b
c
d
e
cad

פלט 1

26

קלט 2

8 8
font
lewin
darko
deon
vanb
johnb
chuckr
tgr
deonjohnbdarkotgrvanbchuckrfontlewin

פלט 2

12451