Năm 2387. Hệ thống cảng dịch chuyển lượng tử liên sao gồm ~m~ trạm đánh số ~0~ đến ~m-1~, kết nối thành một vòng định hướng. Do giới hạn băng thông của đường hầm không-thời gian, từ trạm ~i~, một con tàu chỉ có thể dịch chuyển đến trạm ~(i + d) \bmod m~ với ~d \in \{1, 2, \ldots, k\}~ -- tức là tiến về phía trước từ ~1~ đến ~k~ bước theo chiều kim đồng hồ trên vòng.

Nhà vật lý hàng hải Euler Nakamoto cần kiểm toán hệ thống: có bao nhiêu chuỗi hành trình phân biệt gồm đúng ~n~ lần dịch chuyển, xuất phát từ trạm ~s~ và kết thúc tại trạm ~t~?

Phương án liệt kê trực tiếp rõ ràng không khả thi khi ~n~ lên tới ~10^{18}~. Euler Nakamoto biết rằng ẩn sau bài toán tồn tại một cấu trúc đại số sâu hơn -- nhưng tìm và khai thác nó là nhiệm vụ của bạn.

Đầu vào

Một dòng duy nhất chứa năm số nguyên ~m~, ~k~, ~n~, ~s~, ~t~.

Đầu ra

In ra một số nguyên duy nhất -- số chuỗi hành trình hợp lệ, lấy phần dư khi chia cho ~10^9 + 7~.

Giới hạn

• ~2 \le m \le 100~
• ~1 \le k \le m - 1~
• ~1 \le n \le 10^{18}~
• ~0 \le s, t \le m - 1~

Chấm điểm

• Sub1: ~n \le 10^4~, ~m \le 6~, ~k = 1~
• Sub2: ~n \le 10^6~, ~m \le 10~, ~k \le 4~
• Sub3: ~n \le 10^{18}~, ~m \le 5~, ~k \le m - 1~
• Sub4: ~n \le 10^{18}~, ~m \le 30~, ~k \le m - 1~

Ví dụ 1

Đầu vào

5 2 3 0 0

Đầu ra

3

Giải thích

Với ~m = 5~, ~k = 2~, từ mỗi trạm có thể nhảy ~+1~ hoặc ~+2~ (modulo ~5~). Cần tìm số chuỗi bước nhảy ~(d_1, d_2, d_3)~ với mỗi ~d_i \in \{1, 2\}~ sao cho ~d_1 + d_2 + d_3 \equiv 0 \pmod{5}~.

Tổng ba bước có thể là ~3, 4, 5, 6~. Chỉ tổng ~5~ chia hết cho ~5~, ứng với đúng ba chuỗi:

Ví dụ 2

Đầu vào

4 2 6 1 3

Đầu ra

16