Description

Luogu OJ is certainly a good place, and nodgd wants to share it with friends. So he invited his friends Ciocio and Nicole to practice problems together. Since they love contests, they naturally would not miss such an opportunity for a problem-solving contest!

On day $1$, nodgd, Ciocio, Nicole each solved $1$ problem.

On day $2$, nodgd, Ciocio, Nicole each solved $3$ problems.

They all have strict rules for solving problems and will strictly follow the rules to solve a certain number of problems each day.

1. The number of problems nodgd solves on day $k+2$:

$$a_{k+2}=pa_{k+1}+qa_k+b_{k+1}+c_{k+1}+rk^2+tk+1$$

2. The number of problems Ciocio solves on day $k+2$:

$$b_{k+2}=ub_{k+1}+vb_k+a_{k+1}+c_{k+1}+w^k$$

3. The number of problems Nicole solves on day $k+2$:

$$c_{k+2} = xc_{k+1}+yc_k + a_{k+1} + b_{k+1} + z^k+k+2$$

(All letters $p, q, r, t, u, v, w, x, y, z$ are given constants and are guaranteed to be positive integers.)

Then they started a long problem-solving contest, lasting for $n$ days.

However, time is precious, and nodgd wants to quickly know how many problems each person solves on day $n$.
But nodgd still has a lot of math contest problems, physics contest problems, English contest problems, art contest problems, PE contest problems… to do, so please help him calculate.

Because the results can be large, output the values $\bmod \space m$.

Input Format

The first line contains two positive integers $n, m$.

The second line contains four positive integers $p, q, r, t$.

The third line contains three positive integers $u, v, w$.

The fourth line contains three positive integers $x, y, z$.

Output Format

Output three lines, each containing a name + a space + an integer.
In order: nodgd, Ciocio, Nicole, and their number of problems solved on day $n$ $\bmod \space m$.

4 10007
2 1 1 1
2 2 3
1 1 2

nodgd 74
Ciocio 80
Nicole 59

Hint

For $100\%$ of the testdata, $4 \le n \le 10^{16}$, $2 \le m \le 10^{16}$, $1 \le p, q, r, t, u, v, w, x, y, z \le 100$.

Translated by ChatGPT 5