Bạn có lẽ đã quen thuộc với màn hình hiển thị 7 đoạn được sử dụng rộng rãi để biểu diễn các chữ số trên các thiết bị kỹ thuật số khác nhau, như đồng hồ hoặc máy tính. Do tính đơn giản, tính trực quan và tính thẩm mỹ, thiết kế này đã được chấp nhận trên toàn thế giới. Tuy nhiên, Matej trẻ tuổi lập luận chống lại thiết kế 7 đoạn và cho rằng có thể đạt được chức năng tương tự một cách hiệu quả hơn, chỉ bằng 5 đoạn.

Thiết kế màn hình 5 đoạn - các đoạn được đánh số từ chữ a đến e.

Matej quyết định bắt đầu những bước đầu tiên trong sự nghiệp kinh doanh của mình trong ngành kinh tế phồn thịnh nhất của Croatia, bóng đá. Thiết kế cách mạng của anh sẽ được sử dụng trên bảng thay người trong các trận đấu của 1. HNL. Hiện tại, anh đang làm một bài thuyết trình cho hội đồng quản trị của Hiệp hội Bóng đá Croatia.

Bảng thay người bao gồm ~M~ màn hình 5 đoạn mà, từ trái sang phải, biểu thị các chữ số của một số áo đang mặc của cầu thủ sẽ rời sân. Ở đầu thuyết trình của Matej, bảng thay người đại diện cho số ~X~, và Matej sẽ thực hiện một trong những bước sau mỗi giây:

• Bật một đoạn đang tắt.
• Tắt một đoạn đang bật.

Tổng cộng, Matej sẽ thực hiện ~N~ bước và anh sẽ đảm bảo rằng sau mỗi bước thứ ~K~, bảng sẽ hiển thị một số hợp lệ. Số đó được coi là hợp lệ nếu mỗi chữ số của nó được hiển thị đúng trên màn hình tương ứng (tức là các đoạn đang bật hiển thị một chữ số hợp lệ). Ngoài ra, các số có ít hơn ~M~ chữ số cũng được hiển thị một cách hợp lệ nếu chúng chứa số lượng số ~0~ dẫn đầu phù hợp.

Đối với mỗi trạng thái cuối cùng (số nguyên từ ~0~ đến ~10^M - 1~), Matej quan tâm đến có bao nhiêu cách khác nhau mà anh có thể thực hiện các bước của mình trong buổi thuyết trình để đạt được trạng thái cuối cùng này. Tất nhiên, anh cần tuân theo tất cả các hạn chế được trình bày trong các chương trước. Chúng ta coi hai dãy bước khác nhau nếu, giả sử chúng được thực hiện trên hai bảng khác nhau cùng một lúc, có một thời điểm mà hai bảng đều đại diện cho một trạng thái khác nhau.

Vì số lượng cách khác nhau có thể khá lớn, bạn được yêu cầu tính nó theo modulo ~10^9 + 7~.

Input

Dòng đầu tiên chứa các số nguyên ~M, N, K~ ~(1 \leq K \leq N)~ và ~X~ ~(0 \leq X < 10^M)~ từ mô tả nhiệm vụ.

Output

Trong dòng thứ ~i~, bạn nên đầu ra số lượng cách khác nhau để bảng thay thế hiển thị số ~i - 1~ ở cuối các buổi thuyết trình của Matej. Các số này nên được in modulo ~10^9 + 7~.

Chú ý

• 6 điểm thỏa mãn ~M = 1, 1 \leq N \leq 12~.
• 15 điểm thỏa mãn ~M = 1, 1 \leq N \leq 10^{15}~.
• 12 điểm thỏa mãn ~M = 2, 1 \leq N \leq 1 500, K = N~.
• 12 điểm thỏa mãn ~M = 2, 1 \leq N \leq 10^{15}, 1 \leq K \leq 15~.
• 15 điểm thỏa mãn ~M = 2, 1 \leq N \leq 10^{15}, 1 \leq K \leq 1 500~.
• 40 điểm thỏa mãn ~M = 2, 1 \leq N \leq 10^{15}~.

Sample Input 1

1 2 1 5

Sample Ouput 1

0
0
0
1
0
2
0
0
0
0

Sample Input 2

1 3 3 8

Sample Ouput 2

0
0
0
6
0
13
0
0
0
0

Sample Input 3

1 4 2 4

Sample Ouput 3

24
0
8
0
37
0
4
28
4
24

Giải thích

Giải thích ví dụ đầu tiên: Ở đầu buổi thuyết trình, bảng thay thế (chỉ có một chữ số) hiển thị số 5. Sau mỗi bước di chuyển (do ~K = 1~), bảng phải hiển thị một số hợp lệ. Matej sẽ thực hiện tổng cộng ~N = 2~ bước. Do đó, cuối buổi thuyết trình, bảng có thể hiển thị số 3 hoặc số 5. Số 3 có thể được thu được một cách (5 - 9 - 3) và số 5 có thể được thu được bằng hai cách (5 - 9 - 5 và 5 - 8 - 5).