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

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¹⁸)이 주어진다.</p>

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

출력 형식

첫째 줄에 A_N을 출력한다.

예제 입력

3 5
1 2 3
4 5 6

예제 출력

139