13725번 - RNG

문제

로또를 좋아하는 cubelover는 로또 자동 제출 프로그램에 사용할 랜덤 숫자 생성기(RNG)를 만들기로 했다.

cubelover의 RNG는 아래와 같은 형태의 선형 재귀식으로 나타낼 수 있다.

A_i = (A_i−1 × C₁ + A_i−2 × C₂ + ... + A_i−k × C_k) mod 104857601, (i > k)

N과 A₁, A₂, ..., A_k, 그리고 C₁, C₂, ..., C_k가 주어졌을 때, A_N을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 k와 N (1 ≤ k ≤ 30,000, 1 ≤ N ≤ 10¹⁸)이 주어진다.

둘째 줄에는 A₁, A₂, ..., A_k가 셋째 줄에는 C₁, C₂, ..., C_k가 주어진다. (0 ≤ A_i, C_i < 104857601)

출력

첫째 줄에 A_N을 출력한다.

제한

힌트