众所周知，丢丢陈是位数学巨擘。因此，爱慕他的女生非常之多。他时常因不知如何挑选女生而愁眉苦脸，为此，他发明了斐丢波丢那陈契数列，决定挑选会算这个数列的女生作为女友，该数列定义如下：
其中 是无穷数列，且满足改变 个数之后数列变为无限循环数列，例如。
现在给出数列 的循环节长度 和前 项的内容，并告知将其变为无限循环数列所需改变的项(保证不包括前 项中的任意一项)的位置 和改变前的值 。
现在对给定 ，请帮助女生们求出 对 作除法后的余数。
注意：题中所给下标均从 开始。
测试数据有不超过 组，用 EOF 标志表示输入结束，对于每一组数据满足：
第一行为两个整数 ；
第二行为一个整数 ；
接下来一行共 个整数，表示 的前 项，；
第四行为一个整数 ，表示将其变为无限循环数列所需改变的项的数目；
接下来 行，其中第 行有两个整数 。
对于每组数据，输出一行共一个整数，表示 对 作除法后的余数。
10 8 3 1 2 1 2 7 3 5 4
4
