Công thức truy hồi


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

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

There are no comments at the moment.