
ZOJ Problem Set  2308
The Association for Courtly Manners, an international organization for standardization of social interactions (Better known under the name Absurdly Clumsy Moralists, but let's not take prejudice.) has decided to create a new international standard defining ranks of firepersons (Formerly firemen, but the international standards of course must be politically correct.)  each fireperson receives an integer number describing his rank and when they arrive to a fire, they must enter the fire ground in order of increasing ranks and the low ranked firepersons must keep the fire burning long enough for the high ranked firepersons to enjoy extinguishing sufficiently. The ranks are assigned according to an Arbitrary Constant Multiplier Sequence. An ACMsequence of order k is an integer sequence defined by its first k terms a_{0}, a_{1},...a_{k1} and a recurrence relation a_{n}=��_{1<=i<=k}a_{ni}b_{i} mod 10 000 for n >= k, where the b_{i}'s are integer constants. The ith oldest fireperson then gets rank ai. Your task is to calculate the rank of the ith fireperson, given parameters of the ACMsequence and the number i. Input The input consists of several instances. Each instance is described on a single line containing the following integers separated by a single space: k, a_{0}, , a_{k1}, b_{1}, , b_{k}, i. Here 1 <= k <= 100 is the order of the sequence, 0 <= a_{i} < 10 000 are the first k elements of the sequence, 0 <= b_{i} < 10 000 are the multipliers and 0 <= i < 1 000 000 000 is the number of the element we ask for. The input ends with a line containing a number 0. Output The output consists of several lines corresponding to the instances on the input. The lth line contains a single integer a_{i} which is the ith element of the sequence described by the lth input instance. Sample Input
2 0 1 1 1 6 Sample Output
8 Source: Czech Technical University Open 2004 