{"code":"cntdigraph","name":"Bài toán đếm đường đi trong đồ thị đơn có hướng(*)","description":"Cho một đồ thị đơn, có hướng $G$ với $N$ đỉnh, được đánh số $1,2,3,4,...,N$\r\n\r\nVới mỗi $i,j(1\\le i,j\\le N)$, bạn được cho $1$ số nguyên $a_{i,j}$ thể hiện sự kết nối có hướng giữa hai đỉnh $i$ và $j$. Nếu $a_{i,j}=1$ thì đỉnh $i$ được nối với đỉnh $j$ theo chiều từ $i$ đến $j$, nếu $a_{i,j}=0$ thì không tồn tại kết nối giữa hai đỉnh $i,j$.\r\n\r\n**Yêu cầu:** Tìm số đường khác nhau có độ dài là $K$ trong $G$, biết rằng mỗi con đường này có thể đi qua một cạnh nhiều lần.\r\n\r\nVì đáp số có thể lớn nên cần lấy mod $10^9+7$ trước khi in ra\r\n\r\n

Input

\r\n\r\n+ Dòng thứ nhất chứa hai số nguyên $N,K(1\\le N\\le 50,1\\le K\\le 10^{18})$\r\n\r\n+ $N$ dòng tiếp theo, mỗi dòng chứa $N$ số nguyên $a_{i,1},a_{i,2},...,a_{i,n}(1\\le i\\le N, a_{i,j}\\in \\left\\{0,1\\right\\})$\r\n\r\n

Output

\r\n\r\n+ In ra đáp án sau khi đã lấy mod $10^9+7$\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 3 3\r\n 0 1 0\r\n 1 0 1\r\n 0 0 0\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 3\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n \r\n\r\n Những con đường có độ dài là $3$ là :\r\n\r\n + $1\\rightarrow 2 \\rightarrow 1 \\rightarrow 2$\r\n\r\n + $2\\rightarrow 1 \\rightarrow 2 \\rightarrow 1$\r\n\r\n + $2\\rightarrow 1 \\rightarrow 2 \\rightarrow 3$","points":600.0,"partial":false,"time_limit":2.0,"memory_limit":1048000,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}