Вам надано рядок довжиною \(n\) і словник, що містить \(k\) слів.

Скількома способами можна створити рядок, використовуючи слова?

Обмеження

• \(1≤n≤5000\)
• \(1≤k≤10^5\)
• загальна довжина слів дорівнює не більше \(10^6\)

Формат вхідних даних

Перший рядок містить рядок, що містить \(n\) символів між a–z.

У другому рядку є ціле число \(k\): кількість слів у словнику.

Нарешті є \(k\) рядків, що описують слова. Кожне слово є унікальним і складається з букв a–z.

Формат вихідних даних

Виведіть кількість способів за модулем \(10^9 + 7\).

Пояснення

Можливі шляхи ab+ab+c і abab+c.

Приклад вхідних даних

ababc
4
ab
abab
c
cb

Приклад вихідних даних

2