DFunction

All submissions for this problem are available.
### Read problems statements in [Hindi](http://www.codechef.com/download/translated/COOK111/hindi/DFNC.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/COOK111/mandarin/DFNC.pdf), [Russian](http://www.codechef.com/download/translated/COOK111/russian/DFNC.pdf), [Vietnamese](http://www.codechef.com/download/translated/COOK111/vietnamese/DFNC.pdf), and [Bengali](http://www.codechef.com/download/translated/COOK111/bengali/DFNC.pdf) as well. Dr.D is tired of making up stories, so here is the formal description of this problem : You are given a set $S = \{S_1, S_2, \ldots, S_K\}$, an integer $X$ and a sequence $A_1, A_2, \ldots, A_M$. Let's define an infinite sequence $W_1, W_2, \ldots$: for each valid $i$, $W_i = A_{((i1) \% M) + 1}$. Then, let's define a function $F(i)$ for any nonnegative integer $i$ in the following way:  $F(0) = X$  if $i \in S$, $F(i) = 0$  otherwise, for $i \neq 0$, $F(i) = \left(\sum_{j=1}^i F(ij) \cdot W_j \right) \% (10^9+7)$ Find the value of $F(N)$. ### Input  The first line of the input contains four spaceseparated integers $X$, $K$, $M$ and $N$.  The second line contains $K$ spaceseparated integers $S_1, S_2, \ldots, S_K$.  The third line contains $M$ spaceseparated integers $A_1, A_2, \ldots, A_M$. ### Output Print a single line containing one integer $F(N)$. ### Constraints  $0 \le X \lt 10^9+7$  $0 \le K \le 200$  $1 \le M \le 200$  $0 \le N \le 10^{18}$  $0 \le A_i \lt 10^9+7$ for each valid $i$  $1 \le S_i \le N$ for each valid $i$ ### Example Input ``` 3 1 3 5 4 2 3 1 ``` ### Example Output ``` 231 ```Author:  kmaaszraa 
Editorial  https://discuss.codechef.com/problems/DFNC 
Tags  cook111, kmaaszraa, matrixexpo, mediumhard, taran_1407 
Date Added:  14102019 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 