Nay Dương ngẫm nghĩ lại, thấy đám Miku của Mì cũng xinh đấy chứ. Liếc nhìn đám Miku xinh xinh được Mì đặt gọn gàng trên chiếc giường bé nhỏ, tự nhiên Dương nhận ra bản thân mình cũng bị nghiện từ lúc nào không hay!

Cảm thấy bản thân hơi nặng lời, Dương quyết định xin lỗi Mì và hứa với Mì rằng chừng nào Mì chưa đủ 100 Miku, chừng đó Dương còn tặng Miku cho Mì. Thế là Mì - một cô gái dễ dãi - tha thứ Dương trong phút chốc!

Trong tháng vừa qua, Mì nhận ra ngày nào Dương cũng mua Miku cho mình - ít thì một con, nhiều thì năm con, nên Mì không thể nhớ nổi số lượng Miku mà Mì đang để trong nhà. Và cũng chính vì số lượng Miku tăng quá đột biến trong thời gian ngắn, Mì buộc phải dọn một phòng trống - và phòng này được đặt tên là "Miku's room". Đúng như tên gọi, đây là phòng chỉ dành cho đám con thơ của Mì (ý là đám Miku).

Mì và Dương quyết định xây những chiếc giá để Miku ở căn phòng này, chia thành các ô. Mỗi ô chỉ đặt duy nhất một Miku, được đánh số từ ~1~ đến ~10^n - 1~, không có các chữ số ~0~ không cần thiết ở đầu. Sau khi xem xét một lượt, Mì nhận thấy một quy luật khá thú vị như sau:

Những Miku được định giá là "Miku đắt tiền" đã được xếp vào các ô có chỉ số thỏa mãn tất cả các điều kiện:

• Có đúng ~n~ chữ số.
• Số lượng chữ số ~x~ nằm trong khoảng từ ~l~ tới ~r~.
• Số nhận được chia ~3~ dư ~k~.

Hãy giúp Mì đếm xem liệu Mì có bao nhiêu Miku được định giá là "Miku đắt tiền" nhé!

INPUT

Dòng duy nhất gồm năm số nguyên không âm ~n~, ~l~, ~r~, ~k~ và ~x~. (~1 \le n \le 10^{9}~, ~1 \le l \le r \le n~, ~r - l \le 10^4~, ~k \le 2~, ~x \le 9~).

OUTPUT

Dòng duy nhất là số lượng "Miku đắt tiền".

Vì kết quả có thể rất lớn, hãy in ra phần dư của kết quả khi chia cho ~10^9 + 7~.

SAMPLE INPUT

2 1 2 0 3

SAMPLE OUTPUT

6

Có ~6~ "Miku đắt tiền" là các Miku ở trong các ô ~30, 33, 36, 39, 63, 93~.

SUBTASKS