Chó bủh bủh

Xem PDF

Điểm: 50 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

CarlavierVN sau khi đã chăn được một đàn cừu hồng kha khá, anh bắt đầu cảm thấy mình nên kinh doanh đa cấp. Nhưng do server quá ít người nên anh không biết nên bán cho ai. Chợt hiện lên trong não anh là bruh, wibu rách của A519. Sau một thời gian dài rủ rê, bruh cuối cùng cũng nhận lời, tham gia vào server minecraft mà không hề hay biết rằng anh sắp bị lừa bởi C.A.O. của hội anh em đa cấp.

Qua một vài lần mua cừu hồng của CarlavierVN, bruh bắt đầu thấy có gì mùi gì đó mờ ám quanh đây, liền tậu ngay một đoàn quân cực kì tinh nhuệ và nguy hiểm khôn lường.

Vấn đề đặt ra ở đây là do có quá nhiều chó, anh bắt đầu thấy khó khăn trong việc đặt tên sao cho dễ phân biệt. Cuối cùng anh đưa ra một quyết định rất khôn ngoan, đó là đặt tên cho con chó đầu đàn của mình là \(S (|S| \le 100)\) để nó có thể đi xung quanh và đặt tên cho những con chó khác. Nhưng anh lại gặp một vấn đề mới, khó khăn hơn rất nhiều, đó là đặt tên sao cho ý nghĩa.

Sau một khoảng thời gian AFK suy nghĩ, anh quyết định chọn ra \(N (N \le 10)\) xâu \(T[i] (1 \le i \le N; |T[i]| \le 100)\). Lúc này công việc của anh đã dễ hơn rất nhiều. Anh ghi ra một cái tên \(S\) thật ngầu, sau đó với mỗi xâu \(T[i]\), anh chỉ cần lấy một vài kí tự trong \(T[i]\) sao cho những kí tự được chọn phải xuất hiện trong \(S\) thì đã có \(1\) cách đặt tên cho chú chó.

Vì quá đau não khi phải ngồi liệt kê các từ \(T[i]\) có thể đặt nên giờ bruh không còn chất xám để chọn ra những kí tự để đặt tên nữa, bạn được bruh giao cho nhiệm vụ nói cho anh ấy biết có bao nhiêu cách để lựa chọn đặt tên cho chú chó đầu đàn để anh ấy có một quyết định thông suốt nhất. Note: nếu làm đc thì bruh sẽ trả các bạn \(64\) kim cương.

Input

  • Dòng 1 chứa xâu \(S\).
  • Dòng 2 chứa \(N\).
  • \(N\) dòng tiếp theo, mỗi dòng chứa 1 xâu \(T[i]\).

\(S\) và \(T[i]\) chỉ chứa các kí tự là \(a,b,c,...,y,z\).

Output

  • Số cách đặt tên cho chú chó đầu đàn, nếu không có cách nào thì in ra màn hình \(-1\).

Example

Test 1

Input
abc
2
aa
ab
Output
3
Note

Có thể chọn theo 3 cách sau:

  • Chọn xâu \(‘aa’\) vì kí tự \(‘a’\) xuất hiện trong \(S\).
  • Chọn xâu \(‘ab’\) vì kí tự \(‘a’\) xuất hiện trong \(S\).
  • Chọn xâu \(‘aa’\) và \(‘ab’\) vì kí tự \(‘a’\) và \(‘b’\) xuất hiện trong \(S\).

Bình luận