Trong một thế giới hậu tận thế, Tổ chức Bảo vệ Dị điểm Toàn cầu (SCP) phát hiện ra một loại thông tin sống mới, gọi là Hệ thống Lượng tử Di truyền. Thông tin này được mã hóa thành các chuỗi ký tự và được lưu trữ trong một chuỗi ~s~.

Để kiểm soát dị điểm này, bạn phải đưa nó về trạng thái ổn định. Bạn có thể hoán đổi hai điểm dữ liệu ~s_i~ và ~s_j~ nếu thỏa mãn điều kiện: $$ | c_{pos(s_i)} - c_{pos(s_j)} | \le k. $$

~pos(s_i)~ là chỉ số của kí tự ~s_i~ trong bảng chữ cái (a là ~0~, b là ~1~, v.v.).

Bạn có thể hoán đổi bao nhiêu lần tùy ý.

Mục tiêu là đưa dị điểm ~s~ về trạng thái có thứ tự từ điển nhỏ nhất. Trạng thái này được coi là nền tảng nguyên thủy, vững chắc nhất cho mọi quá trình tổng hợp sau này và được gọi là ~\text{base}~ ~—~ Mẫu hình Thông tin Cơ sở.

Sau khi đã thiết lập thành công ~\text{base}~, Tổ chức cần kích hoạt một quá trình nhân rộng và mở rộng dữ liệu của dị điểm để nghiên cứu sâu hơn. Quá trình này diễn ra qua một số lượng xác định các "Chu kỳ".

Mỗi "Chu kỳ" tuân theo một quy tắc duy nhất, dựa trên một quy tắc nhất định được gọi là Bộ Tán xạ ~h~. Trong mỗi "Chu kỳ", mọi điểm dữ liệu trong chuỗi hiện tại sẽ được thay thế bằng một chuỗi các điểm dữ liệu mới.

Cụ thể, điểm dữ liệu tại vị trí ~i~ trong chuỗi sẽ được thay thế bởi ~h_{pos(s_i)}~ chữ cái liên tiếp tiếp theo trong bảng chữ cái. Nếu quá trình tán xạ vượt quá z, nó sẽ quay vòng lại từ a.

• Ví dụ: a với ~h_{pos(a)} = 3~ sẽ trở thành bcd.
• Ví dụ: y với ~h_{pos(y)} = 3~ sẽ trở thành zab.

Bạn cần tính toán tổng độ dài của chuỗi sau đúng ~m~ chu kỳ, chia dư cho ~10^9 + 7~.

INPUT

Dòng đầu tiên là ba số nguyên ~n, m, k~ ~(1 \le n \le 10^5, 1 \le k \le 10^9, 1 \le m \le 10^{18})~

Dòng thứ hai là xâu ~s~ chỉ bao gôm các kí tự thường

Dòng thứ ba là ~26~ số nguyên ~c_i~ ~(1 \le c_i \le 10^9)~

Dòng thứ tư là ~26~ số nguyên dương ~h_i~ ~(1 \le h_i \le 26)~

OUTPUT

Dòng đầu tiên in ra xâu ~\text{base}~

Dòng tiếp theo in ra tổng độ dài của chuỗi sau đúng ~m~ chu kỳ, chia dư cho ~10^9 + 7~.

SAMPLE INPUT

5 2 1
yycba
1 2 2 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 3 100
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2

SAMPLE OUTPUT

abcyy
7

SUBTASKS

Giải thích

• Hoán đổi vị trí ~3~ với ~4~ ~(c \longleftrightarrow a)~. Vì ~|c_{pos(c)} - c_{pos(a)}| = |2 - 1| = 1 \le 1~.

Chuỗi ~\rightarrow~ y y a c b

• Hoán đổi vị trí ~1~ với ~4~ ~(y \longleftrightarrow c)~. Vì ~|c_{pos(y)} - c_{pos(c)}| = |3 - 2| = 1 \le 1~.

Chuỗi ~\rightarrow~ c y a y b

• Hoán đổi vị trí ~1~ với ~3~ ~(c \longleftrightarrow a)~. Vì ~|c_{pos(c)} - c_{pos(a)}| = |2 - 1| = 1 \le 1~.

Chuỗi ~\rightarrow~ a y c y b

• Hoán đổi vị trí ~2~ với ~5~ ~(y \longleftrightarrow b)~. Vì ~|c_{pos(y)} - c_{pos(b)}| = |3 - 2| = 1 \le 1~.

Chuỗi ~\rightarrow~ a b c y y

Sau các hoán đổi trên ta không thể thu được chuỗi nhỏ hơn theo thứ tự từ điển bằng bất kỳ hoán đổi hợp lệ nào khác.

Vậy ~\text{base}~ = abcyy.

Mở rộng theo ~m = 2~ chu kỳ (theo quy tắc Bộ Tán xạ ~h~) ~—~ chỉ tính độ dài:

Biến đổi lần ~1~ ~(m = 1)~:

• a biến thành b vì ~h_0 = 1~

• b biến thành c vì ~h_1 = 1~

• c biến thành d vì ~h_2 = 1~

• y biến thành z vì ~h_{24} = 1~

• y biến thành z vì ~h_{24}~ ~= 1~

~\rightarrow~ Chuỗi sau biến đổi thứ nhất: bcdzz

Biến đổi lần ~2 (m = 2)~:

• b biến thành c vì ~h_1 = 1~

• c biến thành d vì ~h_2 = 1~

• d biến thành e vì ~h_3 = 1~

• z biến thành ab vì ~h_{25} = 2~

• z biến thành ab vì ~h_{25} = 2~

~\rightarrow~ Chuỗi sau biến đổi thứ hai: cdeabab

Độ dài cuối cùng của chuỗi có ~7~ ký tự.