自动计算机
题号：NC257495
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

“WA/AC 自动机！”

给定一个长度为 m 的序列 a,分别为 a_0,a_1,a_2...a_{m-1}，一开始你拥有一个初始数为 x，你的第 i 次操作会使得 x = (x + a_{(i - 1)\% m} )\%n，请问至少多少次操作才能使 x 变成0。

如果无论多少次操作均无法使 x = 0，那么输出 -1。

输入描述:

第一行输入三个整数 n，m，x。

第二行输入 m 个整数代表序列 a。

保证有 1 \le n,m \le 10^5，0 \le x < n ， 0 \le a_i < n 。

输出描述:

输出一个整数代表答案。
示例1

输入

复制 
8 3 1
1 2 3

输出

复制 
4

说明

一开始 x = 1。
进行第一次操作后 x = 1 + 1 = 2(mod 8)。
进行第二次操作后 x = 2 + 2 = 4(mod 8)。
进行第三次操作后 x = 4 + 3 = 7(mod 8)。
进行第四次操作后 x = 7 + 1 = 0(mod 8)。
示例2

输入

复制 
2 1 0
1

输出

复制 
0
示例3

输入

复制 
4 1 1
2

输出

复制 
-1