Thành phố Hạ Long có ~N~ nút giao thông, được đánh số từ ~1~ đến ~N~. Giữa một số cặp nút giao thông có các con đường hai chiều nối trực tiếp, và việc đi qua mỗi con đường mất đúng ~1~ phút.

Vào một ngày đẹp trời, thầy Hưng quyết định dẫn hai cậu học trò Kiên và Khánh đi dạo khắp thành phố. Xuất phát từ nút giao thông ~S~, cả ba người muốn có một chuyến hành trình kéo dài đúng ~K~ phút, và kết thúc tại nút giao thông ~T~.

Điều đặc biệt là trong quá trình di chuyển, thầy Hưng có thể đi qua bất kỳ nút giao thông nào nhiều lần (kể cả ~S~ và ~T~).

Nhiệm vụ của bạn là đếm xem có bao nhiêu tuyến đường hợp lệ mà thầy Hưng có thể chọn. Vì kết quả có thể rất lớn, hãy in ra phần dư của số đó chia cho ~10^9 + 7~.

Input

• Dòng đầu tiên chứa bốn số nguyên dương ~N, S, T, K~ ~(S, T \leq N \le 50; K \le 10^{18})~.
• Tiếp theo là ~N~ dòng, mỗi dòng chứa ~N~ số nguyên ~c_{i,j}~. Trong đó:
  • ~c_{i,j} = 0~ nếu không có đường;
  • ~c_{i,j} = 1~ nếu tồn tại con đường hai chiều nối trực tiếp giữa nút ~i~ và nút ~j~.

Output

• Một số nguyên duy nhất - phần dư của số tuyến đường thỏa mãn chia cho ~10^9 + 7~.

Sample Input

3 1 1 4
0 1 0
1 0 1
0 1 0

Sample Output

2