結果
問題 | No.1389 Clumsy Calculation |
ユーザー | eSeF |
提出日時 | 2021-02-12 21:24:12 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 145 ms / 2,000 ms |
コード長 | 51,073 bytes |
コンパイル時間 | 1,562 ms |
コンパイル使用メモリ | 123,264 KB |
実行使用メモリ | 44,288 KB |
最終ジャッジ日時 | 2024-07-19 20:08:37 |
合計ジャッジ時間 | 5,245 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 30 ms
19,072 KB |
testcase_01 | AC | 29 ms
19,200 KB |
testcase_02 | AC | 29 ms
18,816 KB |
testcase_03 | AC | 35 ms
19,712 KB |
testcase_04 | AC | 36 ms
19,840 KB |
testcase_05 | AC | 35 ms
19,968 KB |
testcase_06 | AC | 36 ms
19,712 KB |
testcase_07 | AC | 37 ms
19,968 KB |
testcase_08 | AC | 29 ms
19,072 KB |
testcase_09 | AC | 145 ms
44,288 KB |
testcase_10 | AC | 92 ms
33,152 KB |
testcase_11 | AC | 35 ms
19,584 KB |
testcase_12 | AC | 35 ms
19,840 KB |
testcase_13 | AC | 36 ms
19,712 KB |
testcase_14 | AC | 118 ms
37,888 KB |
testcase_15 | AC | 116 ms
38,016 KB |
testcase_16 | AC | 116 ms
38,016 KB |
testcase_17 | AC | 120 ms
38,912 KB |
testcase_18 | AC | 119 ms
38,784 KB |
testcase_19 | AC | 120 ms
38,912 KB |
testcase_20 | AC | 118 ms
39,040 KB |
testcase_21 | AC | 127 ms
38,912 KB |
testcase_22 | AC | 121 ms
38,784 KB |
testcase_23 | AC | 121 ms
38,784 KB |
testcase_24 | AC | 120 ms
38,912 KB |
testcase_25 | AC | 121 ms
38,784 KB |
testcase_26 | AC | 111 ms
36,992 KB |
testcase_27 | AC | 116 ms
38,016 KB |
testcase_28 | AC | 120 ms
39,040 KB |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using System.Collections.Generic;using System.Linq;using System.IO;using System.Text;using System.Numerics;using System.Threading;using System.Runtime.CompilerServices;using System.Diagnostics;using static System.Math;using static System.Array;using static AtCoder.Cout;using static AtCoder.Tool;using static AtCoder.Graph;using ModInt = AtCoder_MOD.ModInt<AtCoder_MOD.Mod1000000007>;using static AtCoder_MOD.ModCalc<AtCoder_MOD.Mod1000000007>;using MOD_Matrix =AtCoder_MOD.MOD_Matrix<AtCoder_MOD.Mod1000000007>;//using ModInt = AtCoder_MOD.ModInt<AtCoder_MOD.Mod998244353>;using static AtCoder_MOD.ModCalc<AtCoder_MOD.Mod998244353>;using MOD_Matrix =AtCoder_MOD.MOD_Matrix<AtCoder_MOD.Mod998244353>;namespace AtCoder{class AC{static readonly int MOD = ModInt.GetMod();const int INF = int.MaxValue / 2;const long SINF = long.MaxValue / 3;static readonly int[] dI = { 0, 1, 0, -1, 1, -1, -1, 1 };static readonly int[] dJ = { 1, 0, -1, 0, 1, 1, -1, -1 };static void Main(string[] args){//var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }; Console.SetOut(sw);/*var th = new Thread(Run, 1 << 26);th.Start();th.Join();*/Run();Console.Out.Flush();}static void Run(){int Testcase = 1;//Testcase = Cin.Int;for (var _ = 0; _ < Testcase; _++) Solve();}static void Solve(){Cin.Scanf(out int N, out long X);var S = Cin.ReadSplitLong;long sum = S.Sum();OutL(sum - (N - 1) * X);}}static class Permutation<T>{private static void Search(List<T[]> perms, Stack<T> stack, T[] a){int N = a.Length;if (N == 0){perms.Add(stack.Reverse().ToArray());}else{var b = new T[N - 1];Array.Copy(a, 1, b, 0, N - 1);for (int i = 0; i < a.Length; ++i){stack.Push(a[i]);Search(perms, stack, b);if (i < b.Length) { b[i] = a[i]; }stack.Pop();}}}public static IEnumerable<T[]> All(IEnumerable<T> src){var perms = new List<T[]>();Search(perms, new Stack<T>(), src.ToArray());return perms;}}public struct Edge{public int from, to;public long w;public double dw;public Edge(int to, long weight) { this.to = to; w = weight; from = -1; dw = -1; }public Edge(int from, int to, long weight) { this.from = from; this.to = to; w = weight; dw = -1; }public Edge(int to, double weight) { this.to = to; from = -1; w = -1; dw = weight; }}public static class Graph{const long inf = long.MaxValue / 3;public static List<List<T>> Gen_Graph<T>(int size){var ret = new List<List<T>>();for (var i = 0; i < size; i++) ret.Add(new List<T>());return ret;}public static long[] Dijkstra(List<List<Edge>> G, int st){int N = G.Count();long[] ret = new long[N];var V = new Priority_Queue<Tuple<long, int>>((x, y) => Sig(x.Item1 - y.Item1));for (var i = 0; i < N; i++) ret[i] = inf;ret[st] = 0; V.Enqueue(new Tuple<long, int>(0, st));while (V.Any()){var cur = V.Dequeue();int v = cur.Item2;long cd = cur.Item1;if (ret[v] < cd) continue;foreach (var ed in G[v]){if (ret[ed.to] > cd + ed.w){ret[ed.to] = cd + ed.w;V.Enqueue(new Tuple<long, int>(ret[ed.to], ed.to));}}}return ret;}public static long[] Bellman_Frod(List<Edge> E, int st, int N, out bool neg_close){var ret = new long[N];for (var i = 0; i < N; i++) ret[i] = inf;ret[st] = 0;for (var i = 0; i < N; i++){foreach (var ed in E){if (ret[ed.from] != inf && ret[ed.to] > ret[ed.from] + ed.w){if (i == N - 1) { neg_close = true; return ret; }ret[ed.to] = ret[ed.from] + ed.w;}}}neg_close = false;return ret;}}public class SCC{int n;struct Edge_S { public int from, to; public Edge_S(int f, int t) { from = f; to = t; } }List<Edge_S> E;int[] id;public SCC(int size) { n = size; E = new List<Edge_S>(); }public void Add_Edge(int from, int to){E.Add(new Edge_S(from, to));}public int[][] Scc_Result(){var start = new int[n + 1];var nxt = new int[E.Count];//var scc = new List<List<int>>();foreach (var ed in E) start[ed.from + 1]++;for (var i = 0; i < n; i++) start[i + 1] += start[i];var itr = new int[n + 1]; for (var i = 0; i <= n; i++) itr[i] = start[i];foreach (var ed in E) nxt[itr[ed.from]++] = ed.to;int now = 0;int[] ord = new int[n];int[] low = new int[n];id = new int[n];var V = new Stack<int>();for (var i = 0; i < n; i++) ord[i] = -1;int nowid = 0;Action<int> DFS = null;DFS = (v) =>{low[v] = ord[v] = now++;V.Push(v);for (var i = start[v]; i < start[v + 1]; i++){var nx = nxt[i];if (ord[nx] == -1){DFS(nx);low[v] = Min(low[v], low[nx]);}else{low[v] = Min(low[v], ord[nx]);}}if (low[v] == ord[v]){while (true){var u = V.Pop();id[u] = nowid;ord[u] = n + 1;if (u == v) break;}nowid++;}};for (var i = 0; i < n; i++) if (ord[i] == -1) DFS(i);for (var i = 0; i < n; i++){id[i] = nowid - 1 - id[i];itr[i] = 0;}var scc = new int[nowid][];for (var i = 0; i < n; i++) itr[id[i]]++;for (var i = 0; i < nowid; i++) scc[i] = new int[itr[i]];for (var i = 0; i < n; i++) scc[id[i]][--itr[id[i]]] = i;/*for (var i = 0; i < nowid; i++) scc.Add(new List<int>());for (var i = 0; i < n; i++) scc[id[i]].Add(i);*/return scc;}public int v_id(int v) => id[v];}public class Two_SAT{// use with SCC Libraryint n;bool[] result;SCC scc;readonly int md;public Two_SAT(int size){n = size;result = new bool[n];scc = new SCC(n << 1);md = n << 1;}public void Add_Closure(int i, bool fi, int j, bool fj){if (!fi) i += n;if (!fj) j += n;scc.Add_Edge((i + n) % md, j);scc.Add_Edge((j + n) % md, i);}public bool Satisfy(){scc.Scc_Result();for (var i = 0; i < n; i++){int j = scc.v_id(i), k = scc.v_id(i + n);if (j == k) return false;result[i] = j > k;}return true;}public bool[] ans() => result;}public class Dinic{readonly int n;const int inf = int.MaxValue / 2;public class Edge_F{public int _to { get; set; }public long _cap { get; set; }public int _rev { get; set; }public Edge_F(int to, long cap, int rev) { _to = to; _cap = cap; _rev = rev; }}List<List<Edge_F>> G;int[] level, itr;public Dinic(int vertice){n = vertice;level = new int[n];itr = new int[n];G = new List<List<Edge_F>>();for (var _ = 0; _ < n; _++) G.Add(new List<Edge_F>());}/*================ ^ _ ^ ==================*///辺の追加(from->to,容量cap)public void Add_Edge(int from, int to, long cap){G[from].Add(new Edge_F(to, cap, G[to].Count()));G[to].Add(new Edge_F(from, 0, G[from].Count() - 1));}//bfsパート(levelの設定)void Bfs(int s){//Fillはバージョン古いと使えないため...for (var i = 0; i < n; i++) level[i] = -1;level[s] = 0;var Q = new Queue<int>();Q.Enqueue(s);while (Q.Any()){int v = Q.Dequeue();foreach (var ed in G[v]){if (ed._cap > 0 && level[ed._to] == -1){level[ed._to] = level[v] + 1;Q.Enqueue(ed._to);}}}}//dfsパート(増加パスの探索)long Dfs(int v, int t, long f){if (v == t) return f;for (var i = itr[v]; i < G[v].Count(); i++){itr[v] = i;var ed = G[v][i];if (ed._cap > 0 && level[v] < level[ed._to]){var d = Dfs(ed._to, t, Min(f, ed._cap));if (d > 0){ed._cap -= d;G[ed._to][ed._rev]._cap += d;return d;}}}return 0;}//s->tの最大流を返す//一般:O(N^2M)//二部グラフマッチング:O(M*Sqrt(N))//辺の容量が全て同じ:O(min(n^{2/3},m^{1/2})*m)//になるらしいpublic long Max_Flow(int s, int t){long ret = 0;for (; ; ){Bfs(s);if (level[t] == -1) return ret;for (var i = 0; i < n; i++) itr[i] = 0;var flow = 0L;do { ret += flow; flow = Dfs(s, t, inf); }while (flow > 0);}}//グラフの状況を返すpublic List<List<Edge_F>> GetGraph() => G;}public class MinCostFlow{const long inf = long.MaxValue / 3;int n;public class Edge{public int _to, _cap, _rev;public long _cost;public bool _isrev;public Edge(int to, int cap, long cost, int rev, bool isrev){_to = to; _cap = cap; _rev = rev; _cost = cost; _isrev = isrev;}}List<List<Edge>> G;public MinCostFlow(int size){n = size;G = new List<List<Edge>>();for (var i = 0; i < n; i++) G.Add(new List<Edge>());}/*辺の追加*/public void Add_Edge(int s, int t, int cap, long cost){G[s].Add(new Edge(t, cap, cost, G[t].Count(), false));G[t].Add(new Edge(s, 0, -cost, G[s].Count() - 1, true));}public long MinCost(int s, int t, int f){long ret = 0;var h = new long[n];var dist = new long[n];var pre_v = new int[n];var pre_e = new int[n];var V = new Priority_Queue<(long, int)>((x, y) => Sig(x.Item1 - y.Item1));while (f > 0){for (var i = 0; i < n; i++) { dist[i] = inf; pre_v[i] = pre_e[i] = -1; }dist[s] = 0;V.Enqueue((0, s));while (V.Any()){var (cd, v) = V.Dequeue();if (dist[v] < cd) continue;for (var i = 0; i < G[v].Count(); i++){var ed = G[v][i];if (ed._cap <= 0) continue;if (dist[ed._to] + h[ed._to] > cd + h[v] + ed._cost){dist[ed._to] = cd + ed._cost + h[v] - h[ed._to];pre_v[ed._to] = v;pre_e[ed._to] = i;V.Enqueue((dist[ed._to], ed._to));}}}if (dist[t] == inf) { return -inf; }for (var i = 0; i < n; i++) h[i] += dist[i];var nowflow = f;for (var now = t; now != s; now = pre_v[now]){nowflow = Min(nowflow, G[pre_v[now]][pre_e[now]]._cap);}f -= nowflow;ret += nowflow * h[t];for (var now = t; now != s; now = pre_v[now]){var rv = G[pre_v[now]][pre_e[now]]._rev;G[pre_v[now]][pre_e[now]]._cap -= nowflow;G[now][rv]._cap += nowflow;}}return ret;}public List<List<Edge>> GetEdges() => G;}public class LCA{List<List<int>> G1;List<List<Edge>> G2;int n;bool isweighted;int[] dist;long[] dist_w;int[,] par;public LCA(List<List<int>> G){G1 = G;G2 = null;n = G1.Count();isweighted = false;dist = new int[n];dist_w = null;par = new int[25, n];}public LCA(List<List<Edge>> G){G1 = null;G2 = G;n = G2.Count();isweighted = true;dist = new int[n];dist_w = new long[n];par = new int[25, n];}public void Lca_Build(int root){for (var i = 0; i < n; i++){dist[i] = -1;if (isweighted) dist_w[i] = -1;}var dfs = new Stack<int>();dfs.Push(root);dist[root] = 0;if (isweighted) dist_w[root] = 0;par[0, root] = -1;while (dfs.Any()){int v = dfs.Pop();if (isweighted){foreach (var ed in G2[v]){if (dist[ed.to] != -1) continue;par[0, ed.to] = v;dist_w[ed.to] = dist[v] + ed.w;dist[ed.to] = dist[v] + 1;dfs.Push(ed.to);}}else{foreach (var nx in G1[v]){if (dist[nx] != -1) continue;par[0, nx] = v;dist[nx] = dist[v] + 1;dfs.Push(nx);}}}for (var i = 1; i < 25; i++){for (var j = 0; j < n; j++){if (par[i - 1, j] == -1) par[i, j] = -1;else par[i, j] = par[i - 1, par[i - 1, j]];}}}public int Lca(int u, int v){if (dist[u] < dist[v]){var kep = u;u = v;v = kep;}for (var i = 0; i < 30; i++){if ((((dist[u] - dist[v]) >> i) & 1) != 0){u = par[i, u];}}if (u == v) return u;for (var i = 24; i >= 0; i--){if (par[i, u] != par[i, v]){u = par[i, u];v = par[i, v];}}return par[0, u];}public int[] GetDist() => dist;public long[] GetWeightedDist() => dist_w;}public class Priority_Queue<T>{private List<T> Q;private readonly Comparison<T> Func_Compare;public Priority_Queue(Comparison<T> comp){Func_Compare = comp;Q = new List<T>();}private void PushHeap(T item){int n = Q.Count();Q.Add(item);while (n != 0){int pIndex = (n - 1) / 2;if (Func_Compare(Q[n], Q[pIndex]) < 0){Swap(n, pIndex);}else { break; }n = pIndex;}}private void PopHeap(){int n = Q.Count() - 1;Q[0] = Q[n];Q.RemoveAt(n);int cur = 0;int comp;while (2 * cur + 1 <= n - 1){int c1 = 2 * cur + 1;int c2 = 2 * (cur + 1);if (c1 == n - 1){comp = c1;}else{comp = Func_Compare(Q[c1], Q[c2]) < 0 ? c1 : c2;}if (Func_Compare(Q[cur], Q[comp]) > 0){Swap(cur, comp);}else { break; }cur = comp;}}[MethodImpl(MethodImplOptions.AggressiveInlining)]private void Swap(int a, int b){T keep = Q[a];Q[a] = Q[b];Q[b] = keep;}[MethodImpl(MethodImplOptions.AggressiveInlining)]public void Enqueue(T value) => PushHeap(value);[MethodImpl(MethodImplOptions.AggressiveInlining)]public T Dequeue(){T ret = Q[0];PopHeap();return ret;}public T Peek() => Q[0];public int Count() => Q.Count();public bool Any() => Q.Any();}public class SegmentTree<T>{//1-indexed typeint n;T[] Tree;Func<T, T, T> f;T ex;int len;[MethodImpl(MethodImplOptions.AggressiveInlining)]public SegmentTree(int size, Func<T, T, T> fun, T exvalue){ex = exvalue;f = fun;len = size;n = 1;while (n < size) n <<= 1;Tree = new T[n << 1];for (var i = 0; i < Tree.Length; i++) Tree[i] = ex;}[MethodImpl(MethodImplOptions.AggressiveInlining)]public void Set_All(){for (var i = n - 1; i >= 1; i--) Tree[i] = f(Tree[i << 1], Tree[(i << 1) | 1]);}[MethodImpl(MethodImplOptions.AggressiveInlining)]public void Assign(int idx, T nxt) => Tree[idx + n] = nxt;[MethodImpl(MethodImplOptions.AggressiveInlining)]public void Update(int idx){int now = idx + n;while (now > 1){now >>= 1;Tree[now] = f(Tree[now << 1], Tree[now << 1 | 1]);}}[MethodImpl(MethodImplOptions.AggressiveInlining)]public void Query_Update(int idx, T nxt){Assign(idx, nxt); Update(idx);}[MethodImpl(MethodImplOptions.AggressiveInlining)]public void Query_Update_func(int idx, T y){Assign(idx, f(Peek(idx), y)); Update(idx);}[MethodImpl(MethodImplOptions.AggressiveInlining)]public T Query_Fold(int l, int r){int L = n + l;int R = n + r;T vL = ex, vR = ex;while (L < R){if (L % 2 == 1){vL = f(vL, Tree[L]);L++;}if (R % 2 == 1){vR = f(Tree[R - 1], vR);R--;}L >>= 1;R >>= 1;}return f(vL, vR);}[MethodImpl(MethodImplOptions.AggressiveInlining)]public T Peek(int idx) => Tree[idx + n];[MethodImpl(MethodImplOptions.AggressiveInlining)]public void Display(int len){for (var i = 0; i < len; i++) Console.Write($"{Tree[i + n]} ");Console.WriteLine();}[MethodImpl(MethodImplOptions.AggressiveInlining)]public int MaxRight(int l, Func<T, bool> ok){if (l == len) { return len; }l += n;var sum = ex;do{while (l % 2 == 0) l >>= 1;if (!ok(f(sum, Tree[l]))){while (l < n){l <<= 1;if (ok(f(sum, Tree[l]))){sum = f(sum, Tree[l++]);}}return l - n;}sum = f(sum, Tree[l++]);} while ((l & (-l)) != l);return len;}[MethodImpl(MethodImplOptions.AggressiveInlining)]public int MinLeft(int r, Func<T, bool> ok){if (r == 0) return 0;r += n;var sum = ex;do{r--;while (r > 1 && (r % 2) != 0) r >>= 1;if (!ok(f(Tree[r], sum))){while (r < n){r = (r << 1 | 1);if (ok(f(Tree[r], sum))){sum = f(Tree[r--], sum);}}return r + 1 - n;}sum = f(Tree[r], sum);} while ((r & (-r)) != r);return 0;}}public class LazySegmentTree<X, A>{int n, L;X[] Tree;A[] lazy;Func<X, X, X> fxx;Func<A, A, A> faa;Func<X, A, X> fxa;X exx;A exa;public LazySegmentTree(int size, Func<X, X, X> funcxx, Func<A, A, A> funcaa, Func<X, A, X> funcxa, X exval, A exlaz){n = size;L = (n << 1) - 1;Tree = new X[n << 1];lazy = new A[n << 1];fxx = funcxx;faa = funcaa;fxa = funcxa;exx = exval;exa = exlaz;for (var i = 0; i <= L; i++) { Tree[i] = exx; lazy[i] = exa; }}public X eval(int id) => fxa(Tree[id], lazy[id]);[MethodImpl(MethodImplOptions.AggressiveInlining)]public void propagate(int id){int h = 0; while ((1 << (h + 1)) <= id) h++;for (var n = h; n > 0; n--){int i = id >> n;Tree[i] = eval(i);lazy[i << 1] = faa(lazy[i << 1], lazy[i]);lazy[i << 1 | 1] = faa(lazy[i << 1 | 1], lazy[i]);lazy[i] = exa;}}[MethodImpl(MethodImplOptions.AggressiveInlining)]public void re_calc(int id){while (id > 1){id >>= 1;Tree[id] = fxx(eval(id << 1), eval(id << 1 | 1));}}public void Range_Update(int l, int r, A op){int L = n + l, R = n + r;int ll = L / (L & (-L));int rr = R / (R & (-R));propagate(ll); propagate(rr - 1);while (L < R){if ((L & 1) == 1){lazy[L] = faa(lazy[L], op);L++;}if ((R & 1) == 1){R--;lazy[R] = faa(lazy[R], op);}L >>= 1; R >>= 1;}re_calc(ll); re_calc(rr - 1);}public X Range_Get(int l, int r){int L = n + l, R = n + r;X vL = exx, vR = exx;propagate(L / (L & (-L)));propagate(R / (R & (-R)) - 1);while (L < R){if ((L & 1) == 1){vL = fxx(vL, eval(L));L++;}if ((R & 1) == 1){R--;vR = fxx(eval(R), vR);}L >>= 1; R >>= 1;}return fxx(vL, vR);}public void Point_Update(int idx, X nxt){int id = idx + n;propagate(id);Tree[id] = nxt;re_calc(id);}/*======================*/public void Assign(int idx, X nxt) => Tree[n + idx] = nxt;public void Set_All(){for (var i = n - 1; i >= 1; i--){Tree[i] = fxx(Tree[i << 1], Tree[i << 1 | 1]);lazy[i] = faa(lazy[i << 1], lazy[i << 1 | 1]);}}public X Peek(int idx) => Range_Get(idx, idx + 1);public void Display(int len){for (var i = 0; i < len; i++) Console.Write($"{Range_Get(i, i + 1)} ");Console.WriteLine();}public void Displayall(){//木の形で表示、nが2冪でない時は注意int e = 0;while ((1 << e) <= n){for (var i = (1 << e); i < (1 << e) + (1 << e); i++) Console.Write($"{Tree[i]}/{lazy[i]} ");Console.WriteLine();e++;}}}public class StringTools{public static int[] Z_algorithm(string S){int L = S.Length;var ret = new int[L];int i = 1, j = 0;ret[0] = L;while (i < L){while (i + j < L && (S[i + j] == S[j])) j++;ret[i] = j;if (j == 0) { i++; continue; }int k = 1;while (i + k < L && (k + ret[k] < j)){ret[i + k] = ret[k];k++;}i += k;j -= k;}return ret;}}public class Rolling_Hash{const ulong m30 = (1UL << 30) - 1;const ulong m31 = (1UL << 31) - 1;const ulong MOD = (1UL << 61) - 1;const ulong Pl = (MOD << 1) << 1;private uint B;private string S;ulong[] hash;ulong[] pw;public Rolling_Hash(string str){S = str;B = (uint)new Random().Next(1 << 12 + 1, int.MaxValue);int L = S.Length;hash = new ulong[L + 1];pw = new ulong[L + 1];hash[0] = 0;pw[0] = 1;for (var i = 0; i < L; i++){hash[i + 1] = CalcMod(Mul(hash[i], B) + S[i]);pw[i + 1] = CalcMod(Mul(pw[i], B));}}[MethodImpl(MethodImplOptions.AggressiveInlining)]public ulong GetHashValue(int idx) => hash[idx];[MethodImpl(MethodImplOptions.AggressiveInlining)]//segment [l,r]public ulong Hash_fold(int l, int r) => CalcMod(Pl + hash[r + 1] - Mul(hash[l], pw[r - l + 1]));[MethodImpl(MethodImplOptions.AggressiveInlining)]//segment[start,start+len-1]public ulong Hash_sub(int start, int len) => CalcMod(Pl + hash[start + len] - Mul(hash[start], pw[len]));[MethodImpl(MethodImplOptions.AggressiveInlining)]public ulong[] GetHashArray() => hash;[MethodImpl(MethodImplOptions.AggressiveInlining)]ulong Mul(ulong a, ulong b){ulong au = a >> 31;ulong ad = a & m31;ulong bu = b >> 31;ulong bd = b & m31;ulong mid = ad * bu + au * bd;ulong midu = mid >> 30;ulong midd = mid & m30;return au * bu * 2 + midu + (midd << 31) + ad * bd;}[MethodImpl(MethodImplOptions.AggressiveInlining)]ulong CalcMod(ulong x){ulong xu = x >> 61;ulong xd = x & MOD;ulong res = xu + xd;if (res >= MOD) res -= MOD;return res;}}public class UnionFind{private int[] parent;private int[] rank;private int[] size;public UnionFind(int n){parent = new int[n];rank = new int[n];size = new int[n];for (var i = 0; i < n; i++){parent[i] = i;rank[i] = 0;size[i] = 1;}}public int Root(int x){return parent[x] == x ? x : parent[x] = Root(parent[x]);}public bool SameRoot(int x, int y){return Root(x) == Root(y);}public void Unite(int x, int y){x = Root(x);y = Root(y);if (x == y) { return; }if (rank[x] < rank[y]){parent[x] = y;size[y] += size[x];size[x] = 0;}else{parent[y] = x;if (rank[x] == rank[y]) { rank[x]++; }size[x] += size[y];size[y] = 0;}}public int SizeOf(int x){return size[Root(x)];}}static class Cin{public static string[] ReadSplit => Console.ReadLine().Split();public static int[] ReadSplitInt => ConvertAll(ReadSplit, int.Parse);public static long[] ReadSplitLong => ConvertAll(ReadSplit, long.Parse);public static double[] ReadSplit_Double => ConvertAll(ReadSplit, double.Parse);public static string Str => Console.ReadLine();public static int Int => int.Parse(Console.ReadLine());public static long Long => long.Parse(Console.ReadLine());public static double Double => double.Parse(Console.ReadLine());public static T Conv<T>(string input){return (T)Convert.ChangeType(input, typeof(T));}public static void Scanf<T>(out T a) => a = Conv<T>(Console.ReadLine());public static void Scanf<T, U>(out T a, out U b){ var q = ReadSplit; a = Conv<T>(q[0]); b = Conv<U>(q[1]); }public static void Scanf<T, U, V>(out T a, out U b, out V c){ var q = ReadSplit; a = Conv<T>(q[0]); b = Conv<U>(q[1]); c = Conv<V>(q[2]); }public static void Scanf<T, U, V, W>(out T a, out U b, out V c, out W d){ var q = ReadSplit; a = Conv<T>(q[0]); b = Conv<U>(q[1]); c = Conv<V>(q[2]); d = Conv<W>(q[3]); }public static void Scanf<T, U, V, W, X>(out T a, out U b, out V c, out W d, out X e){ var q = ReadSplit; a = Conv<T>(q[0]); b = Conv<U>(q[1]); c = Conv<V>(q[2]); d = Conv<W>(q[3]); e = Conv<X>(q[4]); }}static class Cout{public static void OutL(object s) => Console.WriteLine(s);public static void Out_Sep<T>(IEnumerable<T> s) => Console.WriteLine(string.Join(" ", s));public static void Out_Sep<T>(IEnumerable<T> s, string sep) => Console.WriteLine(string.Join($"{sep}", s));public static void Out_Sep(params object[] s) => Console.WriteLine(string.Join(" ", s));public static void Out_One(object s) => Console.Write($"{s} ");public static void Out_One(object s, string sep) => Console.Write($"{s}{sep}");public static void Endl() => Console.WriteLine();}public static class Tool{static public void Initialize<T>(ref T[] array, T initialvalue){array = ConvertAll(array, x => initialvalue);}static public void Swap<T>(ref T a, ref T b){T keep = a;a = b;b = keep;}static public void Display<T>(T[,] array2d, int n, int m){for (var i = 0; i < n; i++){for (var j = 0; j < m; j++){Console.Write($"{array2d[i, j]} ");}Console.WriteLine();}}static public int GcdI(int a,int b){if (a == 0 || b == 0) return Max(a, b);return a % b == 0 ? b : GcdI(b, a % b);}static public long Gcd(long a, long b){if (a == 0 || b == 0) return Max(a, b);return a % b == 0 ? b : Gcd(b, a % b);}static public long Lcm(long a, long b) => a / Gcd(a, b) * b;static public long ExtGcd(long a, long b, ref long x, ref long y){if (b == 0){x = 1; y = 0;return a;}long d = ExtGcd(b, a % b, ref y, ref x);y -= a / b * x;return d;}static public long LPow(int a, int b) => (long)Pow(a, b);static public bool Bit(long x, int dig) => ((1L << dig) & x) != 0;static public int Sig(long a) => a == 0 ? 0 : (int)(a / Abs(a));static public long F_mp(long x, long n, long mod) => n == 0 ? (1 % mod) : (n % 2 == 0 ? F_mp((x * x) % mod, n >> 1, mod) : (x * F_mp(x, n -1, mod)) % mod);static public long F_inv(long x, long mod) => F_mp(x, mod - 2, mod);static public decimal DSqrt(decimal x, decimal epsilon = 0.0M){if (x < 0) throw new OverflowException("Cannot calculate square root from a negative number");decimal current = (decimal)Math.Sqrt((double)x), previous;do{previous = current;if (previous == 0.0M) return 0;current = (previous + x / previous) / 2;}while (Math.Abs(previous - current) > epsilon);return current;}}}namespace AtCoder_MOD{public interface IMod{int Mod { get; }// isprime ?}public interface INTTFriendly{int primitive_root { get; }}public readonly struct Mod1000000007 : IMod{public int Mod => 1000000007;}public readonly struct Mod998244353 : IMod, INTTFriendly{public int Mod => 998244353;public int primitive_root => 3;}public struct ModInt<T> where T : IMod{private int value;// 0 <= x < mod 以外でも OKpublic ModInt(int x){if (x < 0 || x >= default(T).Mod) x %= default(T).Mod;if (x < 0) x += default(T).Mod;value = x;}public ModInt(long x){if (x < 0 || x >= default(T).Mod) x %= default(T).Mod;if (x < 0) x += default(T).Mod;value = (int)x;}// 0 <= x < modpublic ModInt(uint x) => value = (int)x;public static ModInt<T> operator +(ModInt<T> a, ModInt<T> b){var nv = a.value + b.value;if (nv >= default(T).Mod) nv -= default(T).Mod;return new ModInt<T>((uint)nv);}public static ModInt<T> operator ++(ModInt<T> a) => a + 1;public static ModInt<T> operator -(ModInt<T> a, ModInt<T> b){var nv = a.value - b.value;if (nv < 0) nv += default(T).Mod;return new ModInt<T>((uint)nv);}public static ModInt<T> operator --(ModInt<T> a) => a - 1;public static ModInt<T> operator *(ModInt<T> a, ModInt<T> b) => new ModInt<T>((uint)(((long)a.value * b.value) % default(T).Mod));//符号public static ModInt<T> operator +(ModInt<T> a) => a;public static ModInt<T> operator -(ModInt<T> a) => a.value == 0 ? a : new ModInt<T>((uint)(default(T).Mod - a.value));public ModInt<T> Pow(long n){if (n < 0) return Pow(-n).Pow(default(T).Mod - 2);var p = this;var ret = new ModInt<T>(1u);while (n > 0){if ((n & 1) != 0) ret *= p;p *= p;n >>= 1;}return ret;}public ModInt<T> Inverse(){Debug.Assert(value != 0);int x, u, s, t, k;x = 1; u = 0;t = default(T).Mod;s = value;while (t > 0){k = s / t;s -= k * t;(s, t) = (t, s);x -= k * u;(x, u) = (u, x);}return new ModInt<T>((uint)(x < 0 ? x + default(T).Mod : x));}public static ModInt<T> operator /(ModInt<T> a, ModInt<T> b) => (a * b.Inverse());public static bool operator ==(ModInt<T> a, ModInt<T> b) => a.value == b.value;public static bool operator !=(ModInt<T> a, ModInt<T> b) => a.value != b.value;public override bool Equals(object obj) => obj is ModInt<T> && this == (ModInt<T>)obj;public override int GetHashCode() => value.GetHashCode();public override string ToString() => value.ToString();//キャストpublic static implicit operator ModInt<T>(int n) => new ModInt<T>(n);public static implicit operator ModInt<T>(long n) => new ModInt<T>(n);public static explicit operator int(ModInt<T> a) => a.value;public static explicit operator long(ModInt<T> a) => a.value;public static int GetMod() => default(T).Mod;}public static class ModCalc<T> where T : IMod{static readonly List<ModInt<T>> fac = new List<ModInt<T>>() { 1 };static List<ModInt<T>> facinv;static int MAX_N;// Do Use Init(Max_n) Before using other functionspublic static void Init_Mod(int n){MAX_N = n;for (int i = 1; i <= n; i++) fac.Add(fac.Last() * i);facinv = new List<ModInt<T>>() { fac[n].Inverse() };for (int i = n; i > 0; i--) facinv.Add(facinv.Last() * i);facinv.Reverse();}public static void Reset(){MAX_N = -1;fac.Clear();facinv.Clear();}public static ModInt<T> Fac(int n){Debug.Assert(n <= MAX_N);return fac[n];}public static ModInt<T> Finv(int n){Debug.Assert(n <= MAX_N);return facinv[n];}public static ModInt<T> Comb(int n, int r){Debug.Assert(n <= MAX_N);if (n < 0 || r < 0 || n < r) return 0;return fac[n] * facinv[n - r] * facinv[r];}public static ModInt<T> ModPow(long x, long n) => new ModInt<T>(x).Pow(n);public static ModInt<T> ModPow(int x, long n) => new ModInt<T>((uint)x).Pow(n);public static ModInt<T> ModPow(ModInt<T> x, long n) => x.Pow(n);public static ModInt<T> Inv(long x) => new ModInt<T>(x).Inverse();public static ModInt<T> Inv(int x) => new ModInt<T>((uint)x).Inverse();public static List<ModInt<T>> GetFac() => fac;public static List<ModInt<T>> GetFacInv() => facinv;}public struct MOD_Matrix<T> where T : IMod{int n;ModInt<T>[][] mat;public MOD_Matrix(int size){n = size;mat = new ModInt<T>[n][];for (var i = 0; i < n; i++) mat[i] = new ModInt<T>[n];}public MOD_Matrix(int size, ModInt<T>[,] A){n = size;mat = new ModInt<T>[n][];for (var i = 0; i < n; i++) mat[i] = new ModInt<T>[n];for (var i = 0; i < n; i++) for (var j = 0; j < n; j++) mat[i][j] = A[i, j];}public MOD_Matrix(int size, ModInt<T>[][] A){n = size;mat = new ModInt<T>[n][];for (var i = 0; i < n; i++) mat[i] = new ModInt<T>[n];for (var i = 0; i < n; i++) for (var j = 0; j < n; j++) mat[i][j] = A[i][j];}public MOD_Matrix(int size, long[,] A){n = size;mat = new ModInt<T>[n][];for (var i = 0; i < n; i++) mat[i] = new ModInt<T>[n];for (var i = 0; i < n; i++) for (var j = 0; j < n; j++) mat[i][j] = A[i, j];}public MOD_Matrix(int size, long[][] A){n = size;mat = new ModInt<T>[n][];for (var i = 0; i < n; i++) mat[i] = new ModInt<T>[n];for (var i = 0; i < n; i++) for (var j = 0; j < n; j++) mat[i][j] = A[i][j];}public MOD_Matrix(int size, int[,] A){n = size;mat = new ModInt<T>[n][];for (var i = 0; i < n; i++) mat[i] = new ModInt<T>[n];for (var i = 0; i < n; i++) for (var j = 0; j < n; j++) mat[i][j] = A[i, j];}public MOD_Matrix(int size, int[][] A){n = size;mat = new ModInt<T>[n][];for (var i = 0; i < n; i++) mat[i] = new ModInt<T>[n];for (var i = 0; i < n; i++) for (var j = 0; j < n; j++) mat[i][j] = A[i][j];}public ModInt<T>[] this[int id]{set{Debug.Assert(0 <= id && id < n);mat[id] = value;}get{Debug.Assert(0 <= id && id < n);return mat[id];}}public ModInt<T> this[int id1, int id2]{set{Debug.Assert(0 <= id1 && id1 < n && 0 <= id2 && id2 < n);mat[id1][id2] = value;}get{Debug.Assert(0 <= id1 && id1 < n && 0 <= id2 && id2 < n);return mat[id1][id2];}}public static MOD_Matrix<T> operator +(MOD_Matrix<T> A, MOD_Matrix<T> B){Debug.Assert(A.n == B.n);for (var i = 0; i < A.n; i++) for (var j = 0; j < A.n; j++) A[i][j] += B[i][j];return A;}public static MOD_Matrix<T> operator -(MOD_Matrix<T> A, MOD_Matrix<T> B){Debug.Assert(A.n == B.n);for (var i = 0; i < A.n; i++) for (var j = 0; j < A.n; j++) A[i][j] -= B[i][j];return A;}public static MOD_Matrix<T> operator *(MOD_Matrix<T> A, MOD_Matrix<T> B){Debug.Assert(A.n == B.n);var ret = new MOD_Matrix<T>(A.n);for (var i = 0; i < A.n; i++) for (var j = 0; j < A.n; j++){for (var k = 0; k < A.n; k++) ret[i][j] += A[i][k] * B[k][j];}return ret;}public static ModInt<T>[] operator *(MOD_Matrix<T> A, ModInt<T>[] V){Debug.Assert(A.n == V.Length);var ret = new ModInt<T>[A.n];for (var i = 0; i < A.n; i++){for (var j = 0; j < A.n; j++) ret[i] += A[i][j] * V[j];}return ret;}public static MOD_Matrix<T> operator *(MOD_Matrix<T> A, ModInt<T> k){for (var i = 0; i < A.n; i++) for (var j = 0; j < A.n; j++) A[i][j] *= k;return A;}public MOD_Matrix<T> Pow(long K){if (K == 0){var E = new MOD_Matrix<T>(n);for (var i = 0; i < n; i++) E[i][i] = 1;return E;}var ret = new MOD_Matrix<T>(n);var P = this;for (var i = 0; i < n; i++) ret[i][i] = 1;while (K > 0){if ((K & 1) != 0) ret *= P;P *= P; K >>= 1;}return ret;}public static ModInt<T> Solve_Linear_dp(long N, ModInt<T>[] coefs, ModInt<T>[] inits){int K = coefs.Length;if (N < K) return inits[K - 1 - N];var A = new MOD_Matrix<T>(K);for (var i = 0; i < K; i++){if (i == 0) for (var j = 0; j < K; j++) A[i][j] = coefs[j];else A[i][i - 1] = 1;}N -= K - 1;A = A.Pow(N);inits = A * inits;return inits[0];}}public class MOD_NTT<T> where T : IMod, INTTFriendly{private readonly int mod;private readonly int root;public MOD_NTT(){mod = default(T).Mod;root = default(T).primitive_root;}void NTT(ref ModInt<T>[] a, bool rev = false){var n = a.Length;if (n == 1) return;var b = new ModInt<T>[n];var s = new ModInt<T>(root).Pow(rev ? mod - 1 - (mod - 1) / n : (mod - 1) / n);var kp = new List<ModInt<T>>() { 1 };int i, j, k, l, r;for (i = 0; i < (n >> 1); ++i) kp.Add(kp.Last() * s);for (i = 1, l = (n >> 1); i < n; i <<= 1, l >>= 1){for (j = 0, r = 0; j < l; ++j, r += i){for (k = 0, s = kp[i * j]; k < i; ++k){var p = a[k + r]; var q = a[k + r + n / 2];b[k + 2 * r] = (p + q);b[k + 2 * r + i] = ((p - q) * s);}}(a, b) = (b, a);}if (rev){s = new ModInt<T>(n).Inverse();for (i = 0; i < n; ++i) a[i] *= s;}}public ModInt<T>[] Convolution_MOD(ModInt<T>[] a, ModInt<T>[] b){int N = a.Length + b.Length - 1;int t = 1;while (t < N) t <<= 1;var nxa = new ModInt<T>[t];var nxb = new ModInt<T>[t];for (var i = 0; i < a.Length; ++i) nxa[i] = a[i];for (var i = 0; i < b.Length; ++i) nxb[i] = b[i];NTT(ref nxa);NTT(ref nxb);for (var i = 0; i < t; i++) nxa[i] *= nxb[i];NTT(ref nxa, true);return nxa[0..N];}public ModInt<T>[] Convolution_MOD(long[] a, long[] b){int N = a.Length + b.Length - 1;int t = 1;while (t < N) t <<= 1;var nxa = new ModInt<T>[t];var nxb = new ModInt<T>[t];for (var i = 0; i < a.Length; ++i) nxa[i] = a[i];for (var i = 0; i < b.Length; ++i) nxb[i] = b[i];NTT(ref nxa);NTT(ref nxb);for (var i = 0; i < t; i++) nxa[i] *= nxb[i];NTT(ref nxa, true);return nxa[0..N];}}//次数固定、NTT対応modのみpublic struct FormalPowerSeries<T> where T : IMod, INTTFriendly{int n;ModInt<T>[] P;static readonly MOD_NTT<T> C = new MOD_NTT<T>();public FormalPowerSeries(int n){this.n = n;P = new ModInt<T>[n + 1];}public int Length => n;public ModInt<T> this[int id]{set{Debug.Assert(0 <= id && id <= n);P[id] = value;}get{Debug.Assert(0 <= id && id <= n);return P[id];}}//Add//O(min(n,m))public static FormalPowerSeries<T> operator +(FormalPowerSeries<T> F, FormalPowerSeries<T> G){int m = Math.Min(F.Length, G.Length);for (var i = 0; i <= m; i++) F[i] += G[i];return F;}//O(1)public static FormalPowerSeries<T> operator +(FormalPowerSeries<T> F, ModInt<T> a){F[0] += a;return F;}//Subtract//O(min(n,m))public static FormalPowerSeries<T> operator -(FormalPowerSeries<T> F, FormalPowerSeries<T> G){int m = Math.Min(F.Length, G.Length);for (var i = 0; i <= m; i++) F[i] -= G[i];return F;}//O(1)public static FormalPowerSeries<T> operator -(FormalPowerSeries<T> F, ModInt<T> a){F[0] -= a;return F;}// Multiply//O(nlog(n))//下位 n 項のみ残すことに注意public static FormalPowerSeries<T> operator *(FormalPowerSeries<T> F, FormalPowerSeries<T> G){F.P = C.Convolution_MOD(F.P, G.P)[0..(F.n + 1)];return F;}//O(n)public static FormalPowerSeries<T> operator *(FormalPowerSeries<T> F, ModInt<T> a){for (var i = 0; i <= F.n; i++) F[i] *= a;return F;}//Divide//Todo F/=G//O(n+log(mod))public static FormalPowerSeries<T> operator /(FormalPowerSeries<T> F, ModInt<T> a){var inv = a.Inverse();for (var i = 0; i <= F.n; i++) F[i] *= inv;return F;}}}