พิจารณาสตริงตั้งต้น $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