{"problem":{"name":"A < AP","description":{"content":"You are given a permutation $P = (P_1, P_2, \\ldots, P_N)$ of $(1, 2, \\ldots, N)$. Print the number of integer sequences $A = (A_1, A_2, \\ldots, A_N)$ of length $N$ that satisfy both of the conditions ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc151_b"},"statements":[{"statement_type":"Markdown","content":"You are given a permutation $P = (P_1, P_2, \\ldots, P_N)$ of $(1, 2, \\ldots, N)$.\nPrint the number of integer sequences $A = (A_1, A_2, \\ldots, A_N)$ of length $N$ that satisfy both of the conditions below, modulo $998244353$.\n\n*   $1 \\leq A_i \\leq M$ for every $i = 1, 2, \\ldots, N$.\n*   The integer sequence $A$ is lexicographically smaller than the integer sequence $(A_{P_1}, A_{P_2}, \\ldots, A_{P_N})$.\n\nWhat is lexicographical order?An integer sequence $X = (X_1,X_2,\\ldots,X_N)$ is **lexicographically smaller** than an integer sequence $Y = (Y_1,Y_2,\\ldots,Y_N)$ when there is an integer $1 \\leq i \\leq N$ that satisfies both of the conditions below.\n\n*   For all integers $j$ ($1 \\leq j \\leq i-1$), $X_j=Y_j$.\n*   $X_i < Y_i$\n\n## Constraints\n\n*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq M \\leq 10^9$\n*   $1 \\leq P_i \\leq N$\n*   $i \\neq j \\implies P_i \\neq P_j$\n*   All values in the input are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n$P_1$ $P_2$ $\\ldots$ $P_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc151_b","tags":[],"sample_group":[["4 2\n4 1 3 2","6\n\nSix integer sequences $A$ satisfy both of the conditions: $(1, 1, 1, 2)$, $(1, 1, 2, 2)$, $(1, 2, 1, 2)$, $(1, 2, 2, 2)$, $(2, 1, 1, 2)$, and $(2, 1, 2, 2)$.  \nFor instance, when $A = (1, 1, 1, 2)$, we have $(A_{P_1}, A_{P_2}, A_{P_3}, A_{P_4}) = (2, 1, 1, 1)$, which is lexicographically larger than $A$."],["1 1\n1","0"],["20 100000\n11 15 3 20 17 6 1 9 5 19 10 16 7 8 12 2 18 14 4 13","55365742"]],"created_at":"2026-03-03 11:01:14"}}