Under construction

Still being built. Things may change

Logarithm and exponential Taylor polynomials (Small)

Time limit1.5sMemory limit512 MB

Summary
Given a polynomial P(x) with zero constant term and degree at most n, print the Taylor coefficients of ln(1+P(x)) and e^(P(x))-1 modulo 998244353.
Level

Medium5 of 10

Topics
Math, Dynamic programming
Solved
No attempts yet

Problem

The nn-th Taylor polynomial of a function f(x)f(x) at x=0x=0 is

Tnf(x):=∑i=0nf(i)(0)i!xiT_n f(x) := \sum_{i=0}^{n} \frac{f^{(i)}(0)}{i!} x^i

A polynomial P(x)P(x) has degree at most nn, has constant term 00, and is given as a0+a1x+⋯+anxna_0 + a_1x + \cdots + a_nx^n. Compute the nn-th Taylor polynomials of ln⁡(1+P(x))\ln(1+P(x)) and eP(x)−1e^{P(x)}-1.

Input

The first line contains an integer nn (1≤n≤5121 \le n \le 512).

The second line contains n+1n+1 integers a0,a1,⋯ ,ana_0, a_1, \cdots, a_n (0≤ai<9982443530 \le a_i < 998244353, a0=0a_0 = 0).

Output

On the first line, print the n+1n+1 coefficients of the nn-th Taylor polynomial of ln⁡(1+P(x))\ln(1+P(x)) in ascending order of degree.

On the second line, print the n+1n+1 coefficients of the nn-th Taylor polynomial of eP(x)−1e^{P(x)}-1 in ascending order of degree.

Every coefficient is a rational number, so it can be written as an irreducible fraction ab\frac{a}{b}. Print a×b998244351 mod 998244353a \times b^{998244351} \bmod 998244353 for each coefficient.

Examples2

  1. Example 1

    Input
    3
    0 6 0 0
    
    Expected output
    0 6 998244335 72
    0 6 18 36
    
  2. Example 2

    Input
    4
    0 998244352 499122179 831870289 291154613
    
    Expected output
    0 998244352 2 998244350 4
    0 998244352 3 166374051 374341652