描述

宫廷礼仪协会（一个致力于社交互动标准化的国际组织，更广为人知的名称是 “荒谬笨拙的道德家”，但我们不应该有偏见）决定创建一个新的国际标准来定义消防员（以前叫消防员，但国际标准当然必须符合政治正确性）的等级。每个消防员会得到一个整数来表示他的等级。当他们到达火灾现场时，必须按照等级从小到大的顺序进入火场，低等级的消防员必须让火势持续燃烧足够长的时间，以便高等级的消防员能充分享受灭火的过程。等级是根据任意常数乘数序列（ACM - 序列）来分配的。

一个阶数为$k$的 ACM 序列是一个整数序列，由它的前$k$项$a_0, a_1,..., a_{k - 1}$以及递推关系$a_n=(\sum_{1\leq i\leq k}a_{n - i}\times b_i)\mod10000$其中$n\geq k$且$b_i$为整数常数定义。第$i$年长的消防员将获得等级$a_i$。你的任务是根据 ACM 序列的参数和数字$i$，计算第$i$个消防员的等级。

输入

输入包含多个实例。每个实例在一行中描述，包含以下由单个空格分隔的整数：$k, a_0, ..., a_{k - 1}, b_1, ..., b_k, i$。其中$1\leq k\leq100$是序列的阶数，$0\leq a_i <10000$是序列的前$k$个元素，$0\leq b_i <10000$是乘数，$0\leq i < 1000000000$是我们要查询的元素的编号。输入以包含数字$0$的一行结束。

输出

输出包含若干行，对应输入中的实例。第$l$行包含一个整数$a_i$，它是第$l$个输入实例所描述序列的第$i$个元素。

输入数据 1

2 0 1 1 1 6

0

输出数据 1

8

来源2004 年 CTU 公开赛