لدينا $n$ سلسلة أولية مكوّنة من أحرف إنجليزية صغيرة، بحيث لا تكون أي سلسلة أولية بادئة لأي سلسلة أولية أخرى. لنختر الآن $k$ من هذه السلاسل (من دون اختيار أي سلسلة أكثر من مرة)، ونصلها معًا. يمكن تكوين العدد التالي من السلاسل المركّبة بهذه الطريقة:

$$ n \times (n-1) \times (n-2) \times \cdots \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