Lại là một bài toán khác thầy giáo giao cho Per:

Cho ba số nguyên dương ~x~, ~y~, ~z~. Gọi ~XYZ(k)~ là số nguyên dương nhỏ nhất có đúng ~k~ chữ số và chia hết cho cả ~x~, ~y~ và ~z~. Trong trường hợp không tồn tại số như vậy thì ~XYZ(k) = -1~.

Số có đúng ~k~ chữ số là số nằm trong đoạn ~[10^{k-1}, 10^k - 1]~ (không có chữ số ~0~ ở đầu).

Với số ~n~ cho trước, hãy tính ~F(n) = \sum_{k=1}^{n} XYZ(k)~.

Vì đáp án có thể rất lớn nên hãy chia dư cho ~10^9 + 7~.

Dữ liệu vào

Dòng đầu tiên và duy nhất chứa bốn số nguyên ~x~, ~y~, ~z~ và ~n~.

Kết quả

In ra giá trị ~F(n)~ đã chia dư cho ~10^9 + 7~. Đáp án phải là một số trong đoạn ~[0, 10^9 + 6]~.

Ví dụ

Đầu vào:

2 3 5 4

Đầu ra:

1169

Giải thích: Bội chung nhỏ nhất của ~2~, ~3~, ~5~ là ~30~. Không có số một chữ số nào chia hết cho ~30~ nên ~XYZ(1) = -1~. Tiếp theo ~XYZ(2) = 30~, ~XYZ(3) = 120~, ~XYZ(4) = 1020~. Vậy ~F(4) = -1 + 30 + 120 + 1020 = 1169~.

Giới hạn

• ~1 \le x, y, z \le 10^4~
• ~1 \le n \le 16~