Công thức truy hồi
Cho $N$ số nguyên $b_1,b_2,...,b_N$ và $N$ số nguyên $c_1,c_2,..,c_N$. Ta tạo dãy $a$ theo công thức sau:
- $a_i=b_i$ với $i\le N$;
- $a_i=a_{i-1}\times c_1 + ... + a_{i-N} \times c_N$ với $i>N$.
Hãy tìm giá trị của $a_M$.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên $N,M \ (0<N\le 50; 0<M\le 10^{18})$;
- Dòng tiếp theo chứa $N$ số nguyên $b_i \ (0<b_i<10^9)$;
- Dòng tiếp theo chứa $N$ số nguyên $c_i \ (0<c_i<10^9)$.
Kết quả
- Kết quả bài toán sau khi chia lấy dư cho $10^9+3$.
Ví dụ
Ví dụ 1
input
4 7
1 2 1 2
2 1 2 1
output
67
Comments