Cho bốn số nguyên dương ~L~, ~R~, ~X~, ~K~, và một mảng ~v~ có ~|X|~ phần tử (~|X|~ là số chữ số của số ~X~).

Ta định nghĩa độ đẹp của số nguyên dương ~S~ là ~\sum\limits_{i = 1}^{|X|} cnt(i, S) * v_i~, trong đó ~cnt(i, S)~ là số lần xuất hiện của tiền tố độ dài ~i~ của ~X~ trong số ~S~.

Định nghĩa tiền tố độ dài ~i~ của một số ~A~ là số tạo bởi ~i~ chữ số đầu tiên của số ~A~ (ví dụ tiền tố độ dài ~1~ của số ~2306~ là ~2~, tiền tố độ dài ~2~ là ~23~).

Một số được gọi là xấu nếu độ đẹp của nó không lớn hơn ~K~.

Yêu cầu: Đếm số lượng số xấu trong đoạn ~[L, R]~

Input

Gồm hai dòng:

• Dòng thứ nhất chứa ~4~ số nguyên dương ~L~, ~R~, ~X~, và ~K~.
• Dòng thứ hai chứa ~|X|~ số ~v_1, v_2, \dots, v_{|X|}~.

Giới hạn:

• ~1 \leq L \leq R < 10^{200}~
• ~1 \leq X < 10^{20}~
• ~1 \leq K \leq 10^4~
• ~1 \leq v_i \leq 100~ ~\forall~ ~1 \leq i \leq |X|~

Output

Gồm một số nguyên duy nhất là số lượng số xấu trong đoạn ~[L, R]~ lấy phần dư trong phép chia cho ~10^9+7~.

Sample Input 1

203 427 75 3
2 2

Sample Output 1

221