Problem D: Exam

## Problem D: Exam

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2  Solved: 0
[Submit][Status][Web Board]

## Description

$$Alice$$ loves number $$k$$ and base-$$k$$! She wants to give $$Bob$$ an exam about base-$$k$$.
$$Alice$$ gives $$Bob$$ two sequences $$\{a\}=\{a_0,\ldots,a_{k-1}\}$$ and $$\{b\}=\{b_0,\ldots,b_{k-1}\}$$. Obviously, each of them has excatly $$k$$ numbers.
Define function$$\space A(x),B(x),G(x,y),\mathrm{operation} \oplus(xor),\space \mathrm{operation} \space \wedge(and)$$ as follows:
$$A(x)= \prod_{i=0} a[x_{i}],B(x)=\prod_{i=0}b[x_i]$$
$$z=x\oplus y\ :\ z_i=(x_i+y_i) mod\ k$$
$$z=x \wedge y\ :\ z_i=min\{x_i,y_i\}$$
$$G(x,y)=A(x\oplus y)\times B(x \wedge y)$$
Now $$Alice$$ tells $$Bob$$ the number $$k$$ and other three numbers $$s,t,n$$.
$$Bob$$'s task is to calculate {$$\sum_{i=0}^{n} G(i \times s, i \times t)\ mod\ (998244353)$$}.

For example, in Case1, $$k=2,\{a\}=\{1,3\}$$.
we let $$x=11$$, so $$x$$ is $$1011_{(2)},x_0=1,x_1=1,x_2=0,x_3=1$$.
$$A(x)=3 \times 3 \times 1 \times 3=27,B(x)=5 \times 5 \times 1 \times 5=125$$.
and we let $$y=13=1101_{(2)}$$, so $$x \oplus y=110_{2}=6,x \wedge y=1001_{2}=9$$.
Obviously, $$A(1)=3,B(2)=5,G(2,3)=A(2 \oplus 3) \times B(2 \wedge 3)=15$$.

## Input

The first line contains three integer $$k,s,t\ (2\leq k\leq 5,1\leq s,t\leq 30)$$.
The next line contains $$k$$ integers $$a_0,...,a_{k-1}\ (1\leq a_i \leq 100,a_0=1)$$, indicating the sequence $$\{a\}$$.
The next line contains $$k$$ integers $$b_0,...,b_{k-1}\ (1\leq b_i\leq 100,b_0=1)$$, indicating the sequence $$\{b\}$$.
The next line contains a integer $$n\ (0\leq n< k^{200})$$ without leading zeros.
Specially, $$n$$ is given in base-$$k$$ presentation

## Output

A single line, print out the answer.

## Sample Input

2 2 3
1 3
1 5
10

## Sample Output

31

## HINT

Input 2

4 30 30

1 100 100 100

1 100 100 100

123

Output 2

536073375

In case1:

ans=G(0,0)+G(2,3)+G(4,6)

G(0,0)=A(0)*B(0)=1

G(2,3)=A(2 xor 3)*B(2 \& 3)=A(1)*B(2)=3*5=15

G(4,6)=A(4 xor 6)*B(4 \& 6)=A(2)*B(4)=3*5=15

[Submit][Status]