A frightful matrix is a square matrix of order where the first row and the first column are explicitly specified, while the other elements are calculated using a frightful formula which is, actually, a simple recursive rule.
Given two integer sequences and , both of size , as well as integer parameters , and , the frightful matrix is defined as follows:
The first column of the matrix is the sequence : .
The first row of the matrix is the sequence : .
Other elements are calculated using a recursive formula:
Given a frightful matrix, find the value of the element modulo .
The first line contains four integers and — the size of the matrix and the recursion parameters, as described in the problem statement.
The two following lines contain integers and , respectively .
Output a single integer — the value of modulo .