#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")

#define _GNU_SOURCE
#include <assert.h>
#include <inttypes.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// clang-format off
typedef   int8_t      i8;
typedef   int16_t     i16;
typedef   int32_t     i32;
typedef   int64_t     i64;
typedef __int128_t    i128;
typedef   uint8_t     u8;
typedef   uint16_t    u16;
typedef   uint32_t    u32;
typedef   uint64_t    u64;
typedef __uint128_t   u128;
typedef   float       f32;
typedef   double      f64;
typedef   long double f80;

#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define SWAP_REF(a, b)      \
            do {            \
                (a) ^= (b); \
                (b) ^= (a); \
                (a) ^= (b); \
            }               \
            while(0);

#define CTZ32(a)    ((a) ? __builtin_ctz((a)) : (32))
#define CTZ64(a)    ((a) ? __builtin_ctzll((a)) : (64))
#define CLZ32(a)    ((a) ? __builtin_clz((a)) : (32))
#define CLZ64(a)    ((a) ? __builtin_clzll((a)) : (64))
#define POPCNT32(a) ((a) ? __builtin_popcount((a)) : (0))
#define POPCNT64(a) ((a) ? __builtin_popcountll((a)) : (0))
#define MSB32(a)    ((a) ? ((31) - __builtin_clz((a))) : (-1))
#define MSB64(a)    ((a) ? ((63) - __builtin_clzll((a))) : (-1))
#define LSBit(a)    ((a) & (-(a)))
#define CLSBit(a)   ((a) & ((a) - (1)))
    #define _ROTL32_INNER(x, l) (((x) << (l)) | ((x) >> ((-l) & (31))))
    #define _ROTR32_INNER(x, r) (((x) >> (r)) | ((x) << ((-r) & (31))))
    #define _ROTL64_INNER(x, l) (((x) << (l)) | ((x) >> ((-l) & (63))))
    #define _ROTR64_INNER(x, r) (((x) >> (r)) | ((x) << ((-r) & (63))))
#define ROTR32(x, r) (((r) < (0)) ? (_ROTL32_INNER((x), ((u64)(-r) % (32)))) : (_ROTR32_INNER((x), ((r) % (32)))))
#define ROTL32(x, l) ROTR32((x), (-l))
#define ROTR64(x, r) (((r) < (0)) ? (_ROTL64_INNER((x), ((u64)(-r) % (64)))) : (_ROTR64_INNER((x), ((r) % (64)))))
#define ROTL64(x, l) ROTR64((x), (-l))
#define BIT_FLOOR32(a) ((a) ? (1u) << MSB32((a)) : (0))
#define BIT_FLOOR64(a) ((a) ? (1ull) << MSB64((a)) : (0))
#define BIT_CEIL32_REF(a)           \
            do {                    \
                --(a);              \
                (a) |= (a) >> (1);  \
                (a) |= (a) >> (2);  \
                (a) |= (a) >> (4);  \
                (a) |= (a) >> (8);  \
                (a) |= (a) >> (16); \
                (a)++;              \
            } while(0);
#define BIT_CEIL64_REF(a)           \
            do {                    \
                --(a);              \
                (a) |= (a) >> (1);  \
                (a) |= (a) >> (2);  \
                (a) |= (a) >> (4);  \
                (a) |= (a) >> (8);  \
                (a) |= (a) >> (16); \
                (a) |= (a) >> (32); \
                (a)++;              \
            } while(0);

i32 in_i32(void) { i32 c, x = 0, f = 1; while (c = getchar_unlocked(), c < 48 || c > 57) if (c == 45) f = -f; while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return f * x; }
static inline void out_i32_inner(i32 x) { if (x >= 10) out_i32_inner(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); }
void out_i32(i32 x) { if (x < 0) { putchar_unlocked('-'); x = -x; } out_i32_inner(x); }
i64 in_i64(void) { i64 c, x = 0, f = 1; while (c = getchar_unlocked(), c < 48 || c > 57) if (c == 45) f = -f; while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return f * x; }
static inline void out_i64_inner(i64 x) { if (x >= 10) out_i64_inner(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); }
void out_i64(i64 x) { if (x < 0) { putchar_unlocked('-'); x = -x; } out_i64_inner(x); }
u32 in_u32(void) { u32 c, x = 0; while (c = getchar_unlocked(), c < 48 || c > 57); while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return x; }
void out_u32(u32 x) { if (x >= 10) out_u32(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); }
u64 in_u64(void) { u64 c, x = 0; while (c = getchar_unlocked(), c < 48 || c > 57); while (47 < c && c < 58) { x = x * 10 + c - 48; c = getchar_unlocked(); } return x; }
void out_u64(u64 x) { if (x >= 10) out_u64(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); }
void NL(void) { putchar_unlocked('\n'); }
void SP(void) { putchar_unlocked(' '); }

void dump_i32(i32 x) { fprintf(stderr, "\033[1;36m%" PRId32 "\033[0m\n", x); }
void dump_i64(i64 x) { fprintf(stderr, "\033[1;36m%" PRId64 "\033[0m\n", x); }
void dump_u32(u32 x) { fprintf(stderr, "\033[1;36m%" PRIu32 "\033[0m\n", x); }
void dump_u64(u64 x) { fprintf(stderr, "\033[1;36m%" PRIu64 "\033[0m\n", x); }
void dump_i32_array(i32 *a, int a_len) { for (int i = 0; i < a_len; i++) { if (i == a_len - 1) { fprintf(stderr, "\033[1;36m%" PRId32 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRId32 "\033[0m ", a[i]); } } }
void dump_i64_array(i64 *a, int a_len) { for (int i = 0; i < a_len; i++) { if (i == a_len - 1) { fprintf(stderr, "\033[1;36m%" PRId64 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRId64 "\033[0m ", a[i]); } } }
void dump_u32_array(u32 *a, int a_len) { for (int i = 0; i < a_len; i++) { if (i == a_len - 1) { fprintf(stderr, "\033[1;36m%" PRIu32 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRIu32 "\033[0m ", a[i]); } } }
void dump_u64_array(u64 *a, int a_len) { for (int i = 0; i < a_len; i++) { if (i == a_len - 1) { fprintf(stderr, "\033[1;36m%" PRIu64 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRIu64 "\033[0m ", a[i]); } } }
void dump_i32_array_range(i32 *a, int a_len, int l, int r) { if (a_len <= r) { r = a_len - 1; } if (l > r) { return; } for (int i = l; i <= r; i++) { if (i == r) { fprintf(stderr, "\033[1;36m%" PRId32 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRId32 "\033[0m ", a[i]); } } }
void dump_i64_array_range(i64 *a, int a_len, int l, int r) { if (a_len <= r) { r = a_len - 1; } if (l > r) { return; } for (int i = l; i <= r; i++) { if (i == r) { fprintf(stderr, "\033[1;36m%" PRId64 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRId64 "\033[0m ", a[i]); } } }
void dump_u32_array_range(u32 *a, int a_len, int l, int r) { if (a_len <= r) { r = a_len - 1; } if (l > r) { return; } for (int i = l; i <= r; i++) { if (i == r) { fprintf(stderr, "\033[1;36m%" PRIu32 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRIu32 "\033[0m ", a[i]); } } }
void dump_u64_array_range(u64 *a, int a_len, int l, int r) { if (a_len <= r) { r = a_len - 1; } if (l > r) { return; } for (int i = l; i <= r; i++) { if (i == r) { fprintf(stderr, "\033[1;36m%" PRIu64 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRIu64 "\033[0m ", a[i]); } } }
void printb_32bit(u32 v) { u32 mask = (u32)1 << (sizeof(v) * CHAR_BIT - 1); do { putchar_unlocked(mask & v ? '1' : '0'); } while (mask >>= 1); }
void printb_64bit(u64 v) { u64 mask = (u64)1 << (sizeof(v) * CHAR_BIT - 1); do { putchar_unlocked(mask & v ? '1' : '0'); } while (mask >>= 1); }
// clang-format on

static u32 MOD   =  998244353u;
static u32 TWICE = 1996488706u;
static u32 R1    =  301989884u;
static u32 R2    =  932051910u;
static u32 NI    = 3296722945u;
static u32 gs[]  = { 691295370u, 307583142u, 566821959u, 878217029u, 375146819u, 138254384u, 500602490u, 79119218u,  790898700u, 978335284u, 651424567u, 308706579u, 723000027u, 474797508u, 683394121u, 44141573u, 536892010u, 945865189u, 175417726u, 536169764u, 831722880u, 721458245u };
static u32 igs[] = { 306948983u, 888603487u, 138723248u, 65668869u,  842568658u, 953245971u, 195169681u, 118717521u, 792052763u, 828450244u, 908724728u, 218560432u, 628507989u, 248210924u, 566568154u, 6285593u,  82571768u,  49985074u,  225413092u, 349167278u, 61514562u,  763211248u };

static u32 r1_m32(u32 mod)
{
    u32 x = 4294967295u;
    x -= x / mod * mod;
    return x + 1;
}
static u32 r2_m32(u32 mod)
{
    u64 x = 18446744073709551615ul;
    x -= x / mod * mod;
    return x + 1;
}
static u32 ni_m32(u32 mod)
{
    u32 ni = mod, f = 4;
    while (f--) ni *= 2 - mod * ni;
    return ni;
}
static u32 mr_m32(u64 a)
{
    i64 z = (a >> 32) - (((u64)((u32)a * NI) * (u64)MOD) >> 32);;
    return z < 0 ? z + MOD : z;
}
static u32 to_m32(u64 a)
{
    return mr_m32(a * R2);
}
static u32 from_m32(u64 a)
{
    u32 t = mr_m32(a) - MOD;
    return t + (MOD & -(t >> 31));
}
static u32 add_m32(u32 a, u32 b)
{
    a += b - TWICE;
    a += TWICE & -(a >> 31);
    return a;
}
static u32 sub_m32(u32 a, u32 b)
{
    a -= b;
    a += TWICE & -(a >> 31);
    return a;
}
static u32 mul_m32(u64 a, u64 b)
{
    return mr_m32(a * b);
}
static u32 pow_m32(u32 a, size_t b)
{
    return b ? mul_m32(pow_m32(mul_m32(a, a), b >> 1), b & 1 ? a : R1) : R1;
}
static u32 inv_m32(u32 a)
{
    a = from_m32(a);
    int b = MOD, p = 1, q = 0;
    while (b)
    {
        int c = a / b, d = a;
        a = b;
        b = d - c * b;
        d = p;
        p = q;
        q = d - c * q;
    }
    return to_m32(p < 0 ? p + MOD : p);
}

static size_t bsf(size_t x)
{
    __asm__("bsfq %0,%0":"=r"(x):"0"(x));
    return x;
}
static u32 pow_mod(u32 a, size_t b)
{
    return b ? (u64)pow_mod((u64)a * a % MOD, b >> 1) * (b & 1 ? a : 1) % MOD : 1;
}
static u32 primitive_root(void)
{
    if (MOD == 2) return 1;
    if (MOD == 167772161 || MOD == 469762049 || MOD == 998244353) return 3;
    if (MOD == 754974721) return 11;
    const u32 phi = MOD - 1;
    u32 g = 2u, m = phi, p = 5u, q = 7u;
    u32 pr[32] = {2};
    size_t psz = 1;
    while ((m & 1) == false) m >>= 1;
    if (m == m / 3 * 3)
    {
        pr[psz++] = 3;
        do {
            m /= 3;
        } while (m == m / 3 * 3);
    }
    while (p * p <= m)
    {
        if (m == m / p * p)
        {
            pr[psz++] = p;
            do {
                m /= p;
            } while (m == m / p * p);
        }
        p += 6;
        if (m == m / q * q)
        {
            pr[psz++] = q;
            do {
                m /= q;
            } while (m == m / q * q);
        }
        q += 6;
    }
    if (m != 1) pr[psz++] = m;
    while (true)
    {
        bool f = true;
        for (int i = 0; i < psz; ++i)
        {
            if (!f) break;
            f &= (pow_mod(g, phi / pr[i]) != 1);
        }
        if (f) return g;
        ++g;
    }
}
static void init(const u32 mod)
{
    MOD = mod;
    TWICE = mod << 1;
    R1 = r1_m32(MOD);
    R2 = r2_m32(MOD);
    NI = ni_m32(MOD);
    size_t ct2 = bsf(MOD - 1);
    u32 now = R1, inow = R1;
    u32 es[32], ies[32];
    u32 e = pow_m32(to_m32(primitive_root()), (MOD - 1) >> ct2), ie = inv_m32(e);
    for (int i = 0; i < ct2 - 1; ++i)
    {
        es[ct2 - 2 - i] = e;
        e = mul_m32(e, e);
        ies[ct2 - 2 - i] = ie;
        ie = mul_m32(ie, ie);
    }
    for (int i = 0; i < ct2 - 1; ++i)
    {
        gs[i] = mul_m32(es[i], now);
        now = mul_m32(now, ies[i]);
        igs[i] = mul_m32(ies[i], inow);
        inow = mul_m32(inow, es[i]);
    }
}
static void ntt(size_t h, int *A, bool inv)
{
    for (int k = 0; k < h; ++k)
    {
        size_t ph = inv ? h - k : k + 1;
        size_t w = 1 << (ph - 1);
        size_t p = 1 << (h - ph);
        u32 now = R1;
        for (int s = 0; s < w; ++s)
        {
            size_t offset = s << (h - ph + 1);
            for (int i = 0; i < p; ++i)
            {
                unsigned l = A[offset + i], r = A[offset + p + i];
                if (!inv) r = mul_m32(r, now);
                A[offset + i] = add_m32(l, r);
                A[offset + p + i] = sub_m32(l, r);
                if (inv) A[offset + p + i] = mul_m32(A[offset + p + i], now);
            }
            now = mul_m32(now, inv ? igs[CTZ32(~s)] : gs[CTZ32(~s)]);
        }
    }
    if (inv)
    {
        unsigned inv2t = inv_m32(to_m32(1 << h));
        for (int i = 0; i < (1 << h); ++i) A[i] = mul_m32(A[i], inv2t);
    }
}
static void convolute(size_t a_len, size_t b_len, int *A, int *B)
{
    if (!a_len || !b_len) return;
    const size_t c_len = MSB64(a_len + b_len - 1) + 1;
    init(998244353);
    for (int i = 0; i < a_len; ++i) A[i] = to_m32(A[i]);
    for (int i = 0; i < b_len; ++i) B[i] = to_m32(B[i]);
    ntt(c_len, A, false);
    ntt(c_len, B, false);
    for (int i = 0; i < (1 << c_len); ++i) A[i] = mul_m32(A[i], B[i]);
    ntt(c_len, A, true);
    for (int i = 0; i < (1 << c_len); ++i) A[i] = from_m32(A[i]);
}

typedef struct
{
    int *digit;
    size_t len;
    bool sign;
} BigInteger;

static BigInteger ToInt(char *s)
{
    BigInteger b;
    b.sign = (s[0] == '-');
    b.len = strlen(s) - b.sign;
    b.digit = (int *)malloc(b.len * sizeof(int));
    for (int i = 0; i < b.len; ++i)
        b.digit[i] = s[strlen(s) - 1 - i] - '0';
    return b;
}
static char *ToString(BigInteger c)
{
    char *ret = (char *)malloc((c.len + c.sign + 1) * sizeof(char));
    if (c.sign)
    {
        ret[0] = '-';
        if (c.len == 1 && !c.digit[0])
            c.sign = false;
    }
    for (int i = 0; i < c.len; ++i)
        ret[c.sign + i] = c.digit[c.len - 1 - i] + '0';
    ret[c.sign + c.len] = 0;
    c.digit = NULL;
    free(c.digit);
    return ret;
}
static BigInteger Carry(BigInteger fix)
{
    for (int i = 0; i < fix.len - 1; ++i)
    {
        if (fix.digit[i] >= 10)
        {
            fix.digit[i + 1] += fix.digit[i] / 10;
            fix.digit[i] -= fix.digit[i] / 10 * 10;
        }
        if (fix.digit[i] < 0)
        {
            fix.digit[i + 1] += (fix.digit[i] + 1) / 10 - 1;
            fix.digit[i] -= (fix.digit[i] + 1) / 10 * 10 - 10;
        }
    }
    while (fix.digit[fix.len - 1] >= 10)
    {
        int *p = (int *)realloc(fix.digit, (fix.len + 1) * sizeof(int));
        if (p)
        {
            fix.digit = p;
            p = NULL;
            free(p);
        }
        fix.digit[fix.len] = fix.digit[fix.len - 1] / 10;
        fix.digit[fix.len - 1] -= 10 * fix.digit[fix.len];
        fix.len++;
    }
    while (fix.len >= 2 && fix.digit[fix.len - 1] == 0)
        fix.len--;
    return fix;
}
static BigInteger Zero(void)
{
    BigInteger z;
    z.sign = false;
    z.len = 1 - z.sign;
    z.digit = (int *)malloc(z.len * sizeof(int));
    for (int i = 0; i < z.len; ++i)
        z.digit[i] = 0;
    return z;
}
static int Compare(BigInteger a, BigInteger b)
{
    if (a.len > b.len)
        return 1;
    if (a.len < b.len)
        return -1;
    for (int i = 0; i < a.len; ++i)
    {
        if (a.digit[a.len - 1 - i] > b.digit[a.len - 1 - i])
            return 1;
        else if (a.digit[a.len - 1 - i] < b.digit[a.len - 1 - i])
            return -1;
    }
    return 0;
}
static BigInteger Add(BigInteger a, BigInteger b, bool subt)
{
    BigInteger sum;
    sum.len = a.len > b.len ? a.len : b.len;
    sum.digit = (int *)calloc(sum.len + 1, sizeof(int));
    if (a.sign != b.sign)
    {
        if (!subt)
        {
            if (Compare(a, b) < 0)
            {
                sum.sign = b.sign;
                BigInteger c = a;
                a = b;
                b = c;
            }
            else
                sum.sign = a.sign;
            subt=true;
        }
        else
        {
            if (a.sign)
            {
                sum.sign = true;
                subt = false;
            }
            else
                subt = sum.sign = false;
        }
    }
    else
    {
        if (subt)
        {
            if (Compare(a, b) < 0)
            {
                sum.sign = !a.sign;
                BigInteger c = a;
                a = b;
                b = c;
            }
            else
                sum.sign = a.sign;
        }
        if (!subt)
            sum.sign = a.sign;
    }
    for (int i = 0; i < sum.len; ++i)
    {
        if (!subt)
            sum.digit[i] = (i < a.len ? a.digit[i] : 0) + (i < b.len ? b.digit[i] : 0);
        else
            sum.digit[i] = (i < a.len ? a.digit[i] : 0) - (i < b.len ? b.digit[i] : 0);
    }
    a.digit = NULL;
    free(a.digit);
    b.digit = NULL;
    free(b.digit);
    return Carry(sum);
}
static void Naive(size_t n, int *a, int *b, int *c)
{
    for (int i = 0; i < (n << 1); ++i)
        c[i] = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            c[i + j] += a[i] * b[j];
}
static void Karatsuba(size_t n, int *a, int *b, int *c)
{
    if (n <= 1) return Naive(n, a, b, c);
    int *ar = a, *al = a + n / 2;
    int *br = b, *bl = b + n / 2;
    int *asum = c + 5 * n, *bsum = c + 5 * n + n / 2;
    int *d1 = c, *d2 = c + n, *d3 = c + 2 * n;
    for (int i = 0; i < (n >> 1); ++i)
    {
        asum[i] = al[i] + ar[i];
        bsum[i] = bl[i] + br[i];
    }
    Karatsuba(n >> 1, ar, br, d1);
    Karatsuba(n >> 1, al, bl, d2);
    Karatsuba(n >> 1, asum, bsum, d3);
    for (int i = 0; i < n; ++i) d3[i] -= d2[i] + d1[i];
    for (int i = 0; i < n; ++i) c[n / 2 + i] += d3[i];
}
static void ToomCook3(size_t n, int *a, int *b, int *c)
{
    if (n <= 9) return Naive(n, a, b, c);
    size_t cbrt = n / 3;

    int *a_m2 = (int *)calloc(cbrt, sizeof(int));
    int *a_m1 = (int *)calloc(cbrt, sizeof(int));
    int *a_1 = (int *)calloc(cbrt, sizeof(int));

    int *b_m2 = (int *)calloc(cbrt, sizeof(int));
    int *b_m1 = (int *)calloc(cbrt, sizeof(int));
    int *b_1 = (int *)calloc(cbrt, sizeof(int));
    
    int *c_m2 = (int *)calloc(cbrt << 1, sizeof(int));
    int *c_m1 = (int *)calloc(cbrt << 1, sizeof(int));
    int *c_1 = (int *)calloc(cbrt << 1, sizeof(int));
    
    int *c1 = (int *)calloc(cbrt << 1, sizeof(int));
    int *c3 = (int *)calloc(cbrt << 1, sizeof(int));

    for (int i = 0; i < cbrt; ++i)
    {
        a_m2[i] = (a[(cbrt << 1) + i] << 2) - (a[cbrt + i] << 1) + a[i];
        b_m2[i] = (b[(cbrt << 1) + i] << 2) - (b[cbrt + i] << 1) + b[i];
    }
    for (int i = 0; i < cbrt; ++i)
    {
        a_m1[i] = a[(cbrt << 1) + i] - a[cbrt + i] + a[i];
        b_m1[i] = b[(cbrt << 1) + i] - b[cbrt + i] + b[i];
    }
    for (int i = 0; i < cbrt; ++i)
    {
        a_1[i] = a[(cbrt << 1) + i] + a[cbrt + i] + a[i];
        b_1[i] = b[(cbrt << 1) + i] + b[cbrt + i] + b[i];
    }

    ToomCook3(cbrt, a_m2, b_m2, c_m2);
    a_m2 = NULL; free(a_m2);
    b_m2 = NULL; free(b_m2);
    ToomCook3(cbrt, a_m1, b_m1, c_m1);
    a_m1 = NULL; free(a_m1);
    b_m1 = NULL; free(b_m1);
    ToomCook3(cbrt, a, b, c);
    ToomCook3(cbrt, a_1, b_1, c_1);
    a_1 = NULL; free(a_1);
    b_1 = NULL; free(b_1);
    ToomCook3(cbrt, a + (cbrt << 1), b + (cbrt << 1), c + (cbrt << 2));
    
    for (int i = 0; i < (cbrt << 1); ++i)
    {
        c3[i] = -c_m2[i];
        c3[i] += (c_m1[i] << 1) + c_m1[i];
        c3[i] -= (c[i] << 1) + c[i];
        c3[i] += c_1[i];
        c3[i] += (c[(cbrt << 2) + i] << 3) + (c[(cbrt << 2) + i] << 2);
        c3[i] /= 6;
    }
    for (int i = 0; i < (cbrt << 1); ++i)
    {
        c[(cbrt << 1) + i] = (c_m1[i] << 1) + c_m1[i];
        c[(cbrt << 1) + i] -= (c[i] << 2) + (c[i] << 1);
        c[(cbrt << 1) + i] += (c_1[i] << 1) + c_1[i];
        c[(cbrt << 1) + i] -= (c[(cbrt << 2) + i] << 2) + (c[(cbrt << 2) + i] << 1);
        c[(cbrt << 1) + i] /= 6;
    }
    for (int i = 0; i < (cbrt << 1); ++i)
    {
      c1[i] = c_m2[i];
      c1[i] -= (c_m1[i] << 2) + (c_m1[i] << 1);
      c1[i] += (c[i] << 1) + c[i];
      c1[i] += (c_1[i] << 1);
      c1[i] -= (c[(cbrt << 2) + i] << 3) + (c[(cbrt << 2) + i] << 2);
      c1[i] /= 6;
    }

    c_m2 = NULL; free(c_m2);
    c_m1 = NULL; free(c_m1);
    c_1  = NULL; free(c_1);
    for (int i = 0; i < (cbrt << 1); ++i) c[cbrt + i] += c1[i];
    for (int i = 0; i < (cbrt << 1); ++i) c[3 * cbrt + i] += c3[i];
    c1 = NULL; free(c1);
    c3 = NULL; free(c3);
}
static BigInteger Multiply(BigInteger a, BigInteger b)
{
    BigInteger prod;
    prod.sign = a.sign ^ b.sign;
    prod.len = a.len + b.len - 1;
    a.sign = b.sign = false;
    char type = prod.len < 177147 ? 2 : prod.len < 200000 ? 1 : 3;
    switch (type)
    {
        case 1:
            while (prod.len != (prod.len & -prod.len))
            {
                prod.len++;
            }
            break;
        case 2:
            prod.len = 1;
            while (prod.len < a.len + b.len - 1)
            {
                prod.len *= 3;
            }
            break;
        case 3:
            prod.len = MSB64(prod.len) + 1;
            prod.len = 1 << prod.len;
            break;
        default:
            prod.len = a.len + b.len - 1;
    }
    int *u = (int *)calloc((type == 1 ? 6 : 1) * prod.len, sizeof(int));
    int *v = (int *)calloc((type == 1 ? 6 : 1) * prod.len, sizeof(int));
    int *w = (int *)calloc(((type == 1 ? 3 : 1) * prod.len) << 1, sizeof(int));
    for (int i = 0; i < a.len; ++i) u[i] = a.digit[i];
    for (int i = 0; i < b.len; ++i) v[i] = b.digit[i];
    if (type == 1) Karatsuba(prod.len, u, v, w);
    else if (type == 2) ToomCook3(prod.len, u, v, w);
    else
    {
        for (int i = 0; i < a.len; ++i)
            w[i] = a.digit[i];
        convolute(a.len, b.len, w, v);
    }

    u = NULL; free(u);
    v = NULL; free(v);
    
    for (int i = 0; i < (prod.len - 1); ++i) if (w[i] >= 10)
    {
        w[i + 1] += w[i] / 10;
        w[i] -= w[i] / 10 * 10;
    }
    prod.len = a.len + b.len;
    prod.digit = (int *)calloc(prod.len, sizeof(int));
    for (int i = 0; i < prod.len; ++i)
        prod.digit[i] = w[i];
    w = NULL; free(w);
    return Carry(prod);
}
static BigInteger Power(BigInteger b, size_t r)
{
    if (!r)
    {
        BigInteger one = Zero();
        one.digit[0]++;
        return one;
    }
    if (r == 1) return b;
    if (b.digit[b.len - 1] & 1) return Multiply(b, Power(b, --r));
    else
    {
        BigInteger c = Power(b, r >> 1);
        return Multiply(c, c);
    }
}
static void Primary(BigInteger a, BigInteger b, BigInteger p[2])
{
    if (a.len < b.len)
    {
        p[0] = Zero();
        p[1] = a;
        return;
    }
    if (a.len == 1 && !a.digit[0])
    {
        p[0] = a;
        p[1] = Zero();
        return;
    }
    BigInteger apart, quot, r, temp;
    quot.sign = r.sign = apart.sign = temp.sign = false;
    quot.len = a.len - b.len;
    apart.len = temp.len = b.len;
    quot.digit = (int *)calloc(quot.len + 1, sizeof(int));
    apart.digit = (int *)calloc(apart.len + 1, sizeof(int));
    temp.digit = (int *)calloc(temp.len, sizeof(int));
    for (int i = 0; i < apart.len; ++i)
        apart.digit[i] = a.digit[quot.len + i];
    if (Compare(apart, b) >= 0) quot.len++;
    apart.digit = NULL; free(apart.digit);
    if (!quot.len)
    {
        p[0] = Zero();
        p[1] = a;
        return;
    }
    r.len = a.len - quot.len + 1;
    r.digit = (int *)calloc(r.len, sizeof(int));
    for (int i = 0; i < r.len; ++i)
        r.digit[i] = a.digit[quot.len - 1 + i];
    temp = Carry(temp);
    for (int i = 0 ; i < quot.len; ++i)
    {
        quot.digit[quot.len - 1 - i] = 9;
        for (int j = 0; j < 9; ++j)
        {
            temp.digit[0] = j + 1;
            if (Compare(Multiply(b, temp), r) == 1)
            {
                quot.digit[quot.len - 1 - i] = j;
                break;
            }
        }
        temp.digit[0] = quot.digit[quot.len - 1 - i];
        r = Add(r, Multiply(b, temp), true);
        if (i + 1 < quot.len)
        {
            if(r.len == 1 && !r.digit[0])
                r.digit[0] = a.digit[quot.len - 2 - i];
            else
            {
                for (int j = 0; j < r.len; ++j)
                    r.digit[r.len - j] = r.digit[r.len - j - 1];
                r.digit[0] = a.digit[quot.len - 2 - i];
                r.len++;
            }
        }
    }
    temp.digit = NULL; free(temp.digit);
    p[0] = Carry(quot);
    quot.digit = NULL; free(quot.digit);
    while (r.sign)
        r = Add(r, b, false);
    p[1] = Carry(r);
    r.digit = NULL; free(r.digit);
}
static BigInteger Over(BigInteger lhs,long divisor)
{
    long remain = 0;
    lhs.sign ^= (divisor < 0);
    if (divisor < 0) divisor = 0 - divisor;
    for (int i = 0; i < lhs.len; ++i)
    {
        long temp = 10 * remain + lhs.digit[lhs.len - 1 - i];
        lhs.digit[lhs.len - 1 - i] = temp / divisor;
        remain = temp - lhs.digit[lhs.len - 1 - i] * divisor;
    }
    return Carry(lhs);
}
static BigInteger ShiftRight(BigInteger, int, bool);
static BigInteger ShiftLeft(BigInteger a, int n, bool decimal)
{
    if (!n) return a;
    if (n < 0) return ShiftRight(a, -n, decimal);
    if (a.len == 1 && !a.digit[0]) return a;
    if (decimal)
    {
        BigInteger instead;
        instead.sign = a.sign;
        instead.len = a.len + n;
        instead.digit = (int *)calloc(instead.len, sizeof(int));
        for (int i = 0; i < instead.len; ++i)
            instead.digit[instead.len - 1 - i] = i < a.len ? a.digit[a.len - 1 - i] : 0;
        return Carry(instead);
    }
    else
    {
        BigInteger two = Zero();
        two.digit[0] = 2;
        return Multiply(a, Power(two, n));
    }
    return Carry(a);
}
static BigInteger ShiftRight(BigInteger a, int n, bool decimal)
{
    if (!n) return a;
    if (n < 0) return ShiftLeft(a, -n, decimal);
    if (a.len == 1 && !a.digit[0]) return a;
    BigInteger instead;
    instead.sign = a.sign;
    instead.len = a.len;
    instead.digit = (int *)calloc(instead.len, sizeof(int));
    if (decimal)
    {
        if ((size_t)n >= a.len)
            return Zero();
        for (int i = 0; i < n; ++i)
            instead.digit[instead.len - 1 - i] = 0;
        for (int i = 0; i < a.len - n; ++i)
            instead.digit[i] = a.digit[n + i];
    }
    else
    {
        for (int i = 0; i < a.len; ++i)
            instead.digit[i] = a.digit[i];
        while (n > 32)
        {
            instead = Over(instead, 4294967296L);
            n -= 32;
        }
        while (n > 5)
        {
            instead = Over(instead, 32);
            n -= 5;
        }
        while (n--)
            instead = Over(instead, 2);
    }
    return Carry(instead);
}
static size_t BitLength(BigInteger a)
{
    BigInteger dividend;
    dividend.sign = false;
    dividend.len = a.len;
    dividend.digit = (int *)malloc(dividend.len * sizeof(int));
    for (int i = 0; i < dividend.len; ++i)
        dividend.digit[i] = a.digit[i];
    size_t bits = 0;
    long num = 0;
    while (dividend.len > 315650)
    {
        dividend = ShiftRight(dividend, 1 << 20, false);
        bits += 1 << 20;
    }
    while (dividend.len > 39456)
    {
        dividend = ShiftRight(dividend, 1 << 17, false);
        bits += 1 << 17;
    }
    while (dividend.len > 3082)
    {
        dividend = ShiftRight(dividend, (1 << 11) | (1 << 13), false);
        bits += (1 << 11) | (1 << 13);
    }
    while (dividend.len > 308)
    {
        dividend = ShiftRight(dividend, 1 << 10, false);
        bits += 1 << 10;
    }
    while (dividend.len > 38)
    {
        dividend = ShiftRight(dividend, 1 << 7, false);
        bits += 1 << 7;
    }
    while (dividend.len > 9)
    {
        dividend = ShiftRight(dividend, 1 << 5, false);
        bits += 1 << 5;
    }
    for (int i = 0; i < dividend.len; ++i)
    {
        num = (num << 3) + (num << 1) + dividend.digit[dividend.len - 1 - i];
    }
    dividend.digit = NULL; free(dividend.digit);
    return bits + MSB64(num + !a.sign) + 1;
}
const size_t BURNIKELZIEGLERTHRESHOLD = 2;
static void D42(BigInteger, BigInteger,size_t, BigInteger*);
static void D32(BigInteger a, BigInteger b, size_t n, BigInteger c[2])
{
    if (a.len < b.len)
    {
        c[0] = Zero();
        c[1] = a;
        return;
    }
    if (a.len == 1 && !a.digit[0])
    {
        c[0] = a;
        c[1] = a;
        return;
    }
    if (n < BURNIKELZIEGLERTHRESHOLD)
    {
        return Primary(a, b, c);
    }
    BigInteger aHi = ShiftRight(a, n, true);
    BigInteger aTop = ShiftRight(aHi, n, true);
    BigInteger bTop = ShiftRight(b, n, true);
    BigInteger q, r, s;
    BigInteger one = Zero();
    one.digit[0] = 1;
    if (Compare(aTop, bTop) < 0)
    {
        D42(aHi, bTop, n >> 1, c);
        q = c[0];
        r = c[1];
    }
    else
    {
        q = Add(ShiftLeft(one, n, true), one, true);
        r = Add(Add(aHi, ShiftLeft(bTop, n, true), true), bTop, false);
    }
    BigInteger d = Multiply(q, Add(b, ShiftLeft(bTop, n, true), true));
    s = ShiftLeft(r, n, true);
    r.digit = NULL; free(r.digit);
    s = Add(s, Add(a, ShiftLeft(aHi, n, true), true), false);
    aTop.digit = NULL; free(aTop.digit);
    bTop.digit = NULL; free(bTop.digit);
    aHi.digit  = NULL; free(aHi.digit);
    while (Compare(s, d) < 0)
    {
        q = Add(q, one, true);
        s = Add(s, b, false);
    }
    c[1] = Add(s, d, true);
    d.digit = NULL; free(d.digit);
    c[0] = Carry(q);
    q.digit = NULL; free(q.digit);
    s.digit = NULL; free(s.digit);
}
static void D42(BigInteger a, BigInteger b, size_t n, BigInteger c[2])
{
    if (a.len < b.len)
    {
        c[0] = Zero();
        c[1] = a;
        return;
    }
    if (a.len == 1 && !a.digit[0])
    {
        c[0] = a;
        c[1] = a;
        return;
    }
    if (n < BURNIKELZIEGLERTHRESHOLD)
    {
        return Primary(a, b, c);
    }
    BigInteger aHi = ShiftRight(a, n, true);
    D32(aHi, b, n, c);
    BigInteger qHi = ShiftLeft(Carry(c[0]), n, true);
    BigInteger rHi = Add(ShiftLeft(Carry(c[1]), n, true), Add(a, ShiftLeft(aHi, n, true), true), false);
    aHi.digit = NULL; free(aHi.digit);
    D32(rHi, b, n, c);
    c[0] = Add(qHi, Carry(c[0]), false);
    c[1] = Carry(c[1]);
    qHi.digit = NULL; free(qHi.digit);
    rHi.digit = NULL; free(rHi.digit);
}
static void BurnikelZiegler(BigInteger a, BigInteger b, BigInteger c[2])
{
    if (a.len == 1 && !a.digit[0])
    {
        a.digit = NULL; free(a.digit);
        b.digit = NULL; free(b.digit);
        c[0] = c[1] = Zero();
        return;
    }
    if (a.len < b.len)
    {
        b.digit = NULL; free(b.digit);
        c[0] = Zero();
        c[1] = a;
        return;
    }
    if (a.len < BURNIKELZIEGLERTHRESHOLD || b.len < BURNIKELZIEGLERTHRESHOLD)
    {
        return Primary(a, b, c);
    }
    size_t sigma = 1 << MSB64(b.len - ((1ul << MSB64(b.len)) == b.len));
    size_t adjust = (sigma << 1) - b.len;
    size_t t = (a.len + (sigma << 1) - 1) / (sigma << 1);
    a = ShiftLeft(a, adjust, true);
    b = ShiftLeft(b, adjust, true);
    BigInteger aHi = ShiftRight(a, (t < 2 ? 0 : t - 1) * sigma << 1, true);
    BigInteger q = Zero();
    BigInteger r = Add(a, ShiftLeft(aHi, (t < 2 ? 0 : t - 1) * sigma << 1, true), true);
    while (t--)
    {
        if (aHi.len < b.len)
        {
            c[0] = Zero();
            c[1] = aHi;
        }
        else
            D42(aHi, b, sigma, c);
        q = Add(ShiftLeft(q, sigma << 1, true), c[0], false);
        aHi = ShiftLeft(c[1], sigma << 1, true);
        aHi = Add(aHi, ShiftRight(r, (t < 1 ? 0 : t - 1) * sigma << 1, true), false);
        r = Add(r, ShiftLeft(ShiftRight(r, (t < 1 ? 0 : t - 1) * sigma << 1, true), (t < 1 ? 0 : t - 1) * sigma << 1, true), true);
    }
    c[0] = Carry(q);
    c[0].sign = a.sign ^ b.sign;
    c[1] = ShiftRight(c[1], adjust, true);
    aHi.digit = NULL; free(aHi.digit);
    q.digit   = NULL; free(q.digit);
    r.digit   = NULL; free(r.digit);
}
static BigInteger Divide(BigInteger a, BigInteger b, bool mod)
{
    if (a.len == 1 && !a.digit[0])
    {
        a.digit = NULL; free(a.digit);
        b.digit = NULL; free(b.digit);
        return Zero();
    }
    if (a.len < b.len)
    {
        b.digit = NULL; free(b.digit);
        a.sign = false;
        return mod ? a : Zero();
    }
    char v = Compare(a, b);
    if (!v)
    {
        a.digit = NULL; free(a.digit);
        b.digit = NULL; free(b.digit);
        BigInteger one = Zero();
        one.digit[0]++;
        one.sign = a.sign ^ b.sign;
        return mod ? Zero() : one;
    }
    else if(v < 0)
    {
        b.sign = false;
        while (a.sign)
            a = Add(a, b, false);
        return mod ? a : Zero();
    }
    BigInteger c[2];
    bool sign = a.sign ^ b.sign;
    a.sign = b.sign = false;
    BurnikelZiegler(a, b, c);
    c[0].sign = sign;
    return Carry(mod ? c[1] : c[0]);
}

BigInteger Fib0, Fib1, tmp0, tmp1;
void fast_doubling_fibonacci(size_t k)
{
    if (k == 0)
    {
        Fib0 = Zero();
        Fib1 = Zero();
        Fib1.digit[0] = 1;
        Fib1.len = 1;
        Fib1.sign = 0;
        return;
    }
    if (k == 1)
    {
        Fib0 = Zero();
        Fib0.digit[0] = 1;
        Fib0.len = 1;
        Fib0.sign = 0;
        Fib1 = Zero();
        Fib1.digit[0] = 1;
        Fib1.len = 1;
        Fib1.sign = 0;
        return;
    }
    fast_doubling_fibonacci(k >> 1);
    tmp0 = Fib0;
    tmp1 = Fib1;
    BigInteger p = Multiply(Fib0, Fib0);
    BigInteger q = Multiply(Fib1, Fib1);
    Fib0 = tmp0;
    Fib1 = tmp1;
    BigInteger r = Add(Fib0, Fib0, false);
    BigInteger s = Add(Fib1, Fib1, false);
    Fib0 = tmp0;
    Fib1 = tmp1;
    BigInteger x = Add(s, Fib0, true);
    BigInteger y = Add(r, Fib1, false);
    Fib0 = tmp0;
    Fib1 = tmp1;
    if (k & 1)
    {
        Fib0 = Add(p, q, false);
        Fib1 = Multiply(Fib1, y);
    }
    else
    {
        Fib0 = Multiply(Fib0, x);
        Fib1 = Add(p, q, false);
    }
}

int main(void)
{
    size_t L = in_u64();
    if (L == 2)
    {
        printf("3\nINF\n");
    }
    fast_doubling_fibonacci(L);
    if (L & 1)
        printf("%zu\n%s\n", L, ToString(Fib0));
    else
        printf("%zu\n%s\n", L, ToString(Add(Fib0, Multiply(tmp0, tmp0), true)));
    return 0;
}