import macros
macro Please(x): untyped = nnkStmtList.newTree()

Please use Nim-ACL
Please use Nim-ACL
Please use Nim-ACL


import macros;macro ImportExpand(s:untyped):untyped = parseStmt($s[2])
# see https://github.com/zer0-star/Nim-ACL/tree/master/src/atcoder/extra/header/header.nim
ImportExpand "src/atcoder/extra/header/header.nim" <=== "when not declared ATCODER_CHAEMON_HEADER_HPP:\n  const ATCODER_CHAEMON_HEADER_HPP* = 1\n\n  {.hints:off warnings:off assertions:on optimization:speed.}\n  when declared(DO_CHECK):\n    when DO_CHECK:\n      static: echo \"check is on\"\n      {.checks:on.}\n    else:\n      static: echo \"check is off\"\n      {.checks:off.}\n  else:\n    static: echo \"check is on\"\n    {.checks:on.}\n\n  import std/algorithm as algorithm_lib\n  import std/sequtils as sequtils_lib\n  import std/macros as macros_lib\n  import std/math as math_lib\n  import std/sets as sets_lib\n  import std/tables as tables_lib\n  import std/strutils as strutils_lib\n  import std/strformat as strformat_lib\n  import std/options as options_lib\n  import std/bitops as bitops_lib\n  import std/streams as streams_lib\n\n\n  #[ import atcoder/extra/other/internal_sugar ]#\n  when not declared ATCODER_INTERNAL_SUGAR_HPP:\n    const ATCODER_INTERNAL_SUGAR_HPP* = 1\n    import std/macros\n    import std/typetraits\n    \n    proc checkPragma(ex, prag: var NimNode) =\n    #  since (1, 3):\n      block:\n        if ex.kind == nnkPragmaExpr:\n          prag = ex[1]\n          if ex[0].kind == nnkPar and ex[0].len == 1:\n            ex = ex[0][0]\n          else:\n            ex = ex[0]\n    \n    proc createProcType(p, b: NimNode): NimNode {.compileTime.} =\n      result = newNimNode(nnkProcTy)\n      var\n        formalParams = newNimNode(nnkFormalParams).add(b)\n        p = p\n        prag = newEmptyNode()\n    \n      checkPragma(p, prag)\n    \n      case p.kind\n      of nnkPar, nnkTupleConstr:\n        for i in 0 ..< p.len:\n          let ident = p[i]\n          var identDefs = newNimNode(nnkIdentDefs)\n          case ident.kind\n          of nnkExprColonExpr:\n            identDefs.add ident[0]\n            identDefs.add ident[1]\n          else:\n            identDefs.add newIdentNode(\"i\" & $i)\n            identDefs.add(ident)\n          identDefs.add newEmptyNode()\n          formalParams.add identDefs\n      else:\n        var identDefs = newNimNode(nnkIdentDefs)\n        identDefs.add newIdentNode(\"i0\")\n        identDefs.add(p)\n        identDefs.add newEmptyNode()\n        formalParams.add identDefs\n    \n      result.add formalParams\n      result.add prag\n    \n    macro `=>`*(p, b: untyped): untyped =\n      ## Syntax sugar for anonymous procedures.\n      ## It also supports pragmas.\n      var\n        params = @[ident\"auto\"]\n        name = newEmptyNode()\n        kind = nnkLambda\n        pragma = newEmptyNode()\n        p = p\n    \n      checkPragma(p, pragma)\n    \n      if p.kind == nnkInfix and p[0].kind == nnkIdent and p[0].eqIdent\"->\":\n        params[0] = p[2]\n        p = p[1]\n    \n      checkPragma(p, pragma) # check again after -> transform\n  #    since (1, 3):\n      block:\n  #      if p.kind == nnkCall:\n        if p.kind in {nnkCall, nnkObjConstr}:\n          # foo(x, y) => x + y\n          kind = nnkProcDef\n          name = p[0]\n          let newP = newNimNode(nnkPar)\n          for i in 1..<p.len:\n            newP.add(p[i])\n          p = newP\n    \n      case p.kind\n      of nnkPar, nnkTupleConstr:\n        var untypedBeforeColon = 0\n        for i, c in p:\n          var identDefs = newNimNode(nnkIdentDefs)\n          case c.kind\n          of nnkExprColonExpr:\n            let t = c[1]\n    #        since (1, 3):\n            block:\n              # + 1 here because of return type in params\n              for j in (i - untypedBeforeColon + 1) .. i:\n                params[j][1] = t\n            untypedBeforeColon = 0\n            identDefs.add(c[0])\n            identDefs.add(t)\n            identDefs.add(newEmptyNode())\n          of nnkIdent:\n            identDefs.add(c)\n            identDefs.add(newIdentNode(\"auto\"))\n            identDefs.add(newEmptyNode())\n            inc untypedBeforeColon\n          of nnkInfix:\n            if c[0].kind == nnkIdent and c[0].eqIdent\"->\":\n              var procTy = createProcType(c[1], c[2])\n              params[0] = procTy[0][0]\n              for i in 1 ..< procTy[0].len:\n                params.add(procTy[0][i])\n            else:\n              error(\"Expected proc type (->) got (\" & c[0].strVal & \").\", c)\n            break\n          else:\n            error(\"Incorrect procedure parameter list.\", c)\n          params.add(identDefs)\n      of nnkIdent:\n        var identDefs = newNimNode(nnkIdentDefs)\n        identDefs.add(p)\n        identDefs.add(ident\"auto\")\n        identDefs.add(newEmptyNode())\n        params.add(identDefs)\n      else:\n        error(\"Incorrect procedure parameter list.\", p)\n      result = newProc(body = b, params = params,\n                       pragmas = pragma, name = name,\n                       procType = kind)\n  \n    macro `->`*(p, b: untyped): untyped =\n      result = createProcType(p, b)\n    \n    macro dump*(x: untyped): untyped =\n      let s = x.toStrLit\n      let r = quote do:\n        debugEcho `s`, \" = \", `x`\n      return r\n    \n    # TODO: consider exporting this in macros.nim\n    proc freshIdentNodes(ast: NimNode): NimNode =\n      # Replace NimIdent and NimSym by a fresh ident node\n      # see also https://github.com/nim-lang/Nim/pull/8531#issuecomment-410436458\n      proc inspect(node: NimNode): NimNode =\n        case node.kind:\n        of nnkIdent, nnkSym:\n          result = ident($node)\n        of nnkEmpty, nnkLiterals:\n          result = node\n        else:\n          result = node.kind.newTree()\n          for child in node:\n            result.add inspect(child)\n      result = inspect(ast)\n    \n    macro capture*(locals: varargs[typed], body: untyped): untyped =\n      var params = @[newIdentNode(\"auto\")]\n      let locals = if locals.len == 1 and locals[0].kind == nnkBracket: locals[0]\n                   else: locals\n      for arg in locals:\n        if arg.strVal == \"result\":\n          error(\"The variable name cannot be `result`!\", arg)\n        params.add(newIdentDefs(ident(arg.strVal), freshIdentNodes getTypeInst arg))\n      result = newNimNode(nnkCall)\n      result.add(newProc(newEmptyNode(), params, body, nnkProcDef))\n      for arg in locals: result.add(arg)\n    \n    #[ import atcoder/extra/other/internal_underscored_calls ]#\n    when not declared ATCODER_INTERNAL_UNDERSCORED_CALLS_HPP:\n      const ATCODER_INTERNAL_UNDERSCORED_CALLS_HPP* = 1\n      import macros\n    \n      proc underscoredCall(n, arg0: NimNode): NimNode =\n        proc underscorePos(n: NimNode): int =\n          for i in 1 ..< n.len:\n            if n[i].eqIdent(\"_\"): return i\n          return 0\n    \n        if n.kind in nnkCallKinds:\n          result = copyNimNode(n)\n          result.add n[0]\n    \n          let u = underscorePos(n)\n          for i in 1..u-1: result.add n[i]\n          result.add arg0\n          for i in u+1..n.len-1: result.add n[i]\n        elif n.kind in {nnkAsgn, nnkExprEqExpr}:\n          var field = n[0]\n          if n[0].kind == nnkDotExpr and n[0][0].eqIdent(\"_\"):\n            # handle _.field = ...\n            field = n[0][1]\n          result = newDotExpr(arg0, field).newAssignment n[1]\n        else:\n          # handle e.g. 'x.dup(sort)'\n          result = newNimNode(nnkCall, n)\n          result.add n\n          result.add arg0\n    \n      proc underscoredCalls*(result, calls, arg0: NimNode) =\n        expectKind calls, {nnkArgList, nnkStmtList, nnkStmtListExpr}\n    \n        for call in calls:\n          if call.kind in {nnkStmtList, nnkStmtListExpr}:\n            underscoredCalls(result, call, arg0)\n          else:\n            result.add underscoredCall(call, arg0)\n      discard\n  \n    macro dup*[T](arg: T, calls: varargs[untyped]): T =\n      result = newNimNode(nnkStmtListExpr, arg)\n      let tmp = genSym(nskVar, \"dupResult\")\n      result.add newVarStmt(tmp, arg)\n      underscoredCalls(result, calls, tmp)\n      result.add tmp\n    \n    \n    proc transLastStmt(n, res, bracketExpr: NimNode): (NimNode, NimNode, NimNode) =\n      # Looks for the last statement of the last statement, etc...\n      case n.kind\n      of nnkIfExpr, nnkIfStmt, nnkTryStmt, nnkCaseStmt:\n        result[0] = copyNimTree(n)\n        result[1] = copyNimTree(n)\n        result[2] = copyNimTree(n)\n        for i in ord(n.kind == nnkCaseStmt)..<n.len:\n          (result[0][i], result[1][^1], result[2][^1]) = transLastStmt(n[i], res, bracketExpr)\n      of nnkStmtList, nnkStmtListExpr, nnkBlockStmt, nnkBlockExpr, nnkWhileStmt,\n          nnkForStmt, nnkElifBranch, nnkElse, nnkElifExpr, nnkOfBranch, nnkExceptBranch:\n        result[0] = copyNimTree(n)\n        result[1] = copyNimTree(n)\n        result[2] = copyNimTree(n)\n        if n.len >= 1:\n          (result[0][^1], result[1][^1], result[2][^1]) = transLastStmt(n[^1], res, bracketExpr)\n      of nnkTableConstr:\n        result[1] = n[0][0]\n        result[2] = n[0][1]\n        if bracketExpr.len == 1:\n          bracketExpr.add([newCall(bindSym\"typeof\", newEmptyNode()), newCall(\n              bindSym\"typeof\", newEmptyNode())])\n        template adder(res, k, v) = res[k] = v\n        result[0] = getAst(adder(res, n[0][0], n[0][1]))\n      of nnkCurly:\n        result[2] = n[0]\n        if bracketExpr.len == 1:\n          bracketExpr.add(newCall(bindSym\"typeof\", newEmptyNode()))\n        template adder(res, v) = res.incl(v)\n        result[0] = getAst(adder(res, n[0]))\n      else:\n        result[2] = n\n        if bracketExpr.len == 1:\n          bracketExpr.add(newCall(bindSym\"typeof\", newEmptyNode()))\n        template adder(res, v) = res.add(v)\n        result[0] = getAst(adder(res, n))\n    \n    macro collect*(init, body: untyped): untyped =\n      # analyse the body, find the deepest expression 'it' and replace it via\n      # 'result.add it'\n      let res = genSym(nskVar, \"collectResult\")\n      expectKind init, {nnkCall, nnkIdent, nnkSym}\n      let bracketExpr = newTree(nnkBracketExpr,\n        if init.kind == nnkCall: init[0] else: init)\n      let (resBody, keyType, valueType) = transLastStmt(body, res, bracketExpr)\n      if bracketExpr.len == 3:\n        bracketExpr[1][1] = keyType\n        bracketExpr[2][1] = valueType\n      else:\n        bracketExpr[1][1] = valueType\n      let call = newTree(nnkCall, bracketExpr)\n      if init.kind == nnkCall:\n        for i in 1 ..< init.len:\n          call.add init[i]\n      result = newTree(nnkStmtListExpr, newVarStmt(res, call), resBody, res)\n    discard\n#  import std/sugar\n  #[ import atcoder/extra/other/reader ]#\n  when not declared ATCODER_READER_HPP:\n    const ATCODER_READER_HPP* = 1\n    import streams\n    import strutils\n    import sequtils\n  #  proc scanf*(formatstr: cstring){.header: \"<stdio.h>\", varargs.}\n    #proc getchar(): char {.header: \"<stdio.h>\", varargs.}\n  #  proc nextInt*(): int = scanf(\"%lld\",addr result)\n  #  proc nextFloat*(): float = scanf(\"%lf\",addr result)\n    proc nextString*(f:auto = stdin): string =\n      var get = false\n      result = \"\"\n      while true:\n        let c = f.readChar\n        #doassert c.int != 0\n        if c.int > ' '.int:\n          get = true\n          result.add(c)\n        elif get: return\n    proc nextInt*(f:auto = stdin): int = parseInt(f.nextString)\n    proc nextFloat*(f:auto = stdin): float = parseFloat(f.nextString)\n  #  proc nextString*():string = stdin.nextString()\n  \n    proc toStr*[T](v:T):string =\n      proc `$`[T](v:seq[T]):string =\n        v.mapIt($it).join(\" \")\n      return $v\n    \n    proc print0*(x: varargs[string, toStr]; sep:string):string{.discardable.} =\n      result = \"\"\n      for i,v in x:\n        if i != 0: addSep(result, sep = sep)\n        add(result, v)\n      result.add(\"\\n\")\n      stdout.write result\n    \n    var print*:proc(x: varargs[string, toStr])\n    print = proc(x: varargs[string, toStr]) =\n      discard print0(@x, sep = \" \")\n    discard\n  #[ import atcoder/extra/other/cfor ]#\n  when not declared ATCODER_CFOR_HPP:\n    import std/macros\n    const ATCODER_CFOR_HPP* = 1\n    macro For*(preLoop, condition, postLoop, body:untyped):NimNode =\n      var\n        preLoop = if preLoop.repr == \"()\": ident(\"discard\") else: preLoop\n        condition = if condition.repr == \"()\": ident(\"true\") else: condition\n        postLoop = if postLoop.repr == \"()\": ident(\"discard\") else: postLoop\n      quote do:\n        `preLoop`\n        var start_cfor {.gensym.} = true\n        while true:\n          if start_cfor:\n            start_cfor = false\n          else:\n            `postLoop`\n          if not `condition`:\n            break\n          `body`\n    template cfor*(preLoop, condition, postLoop, body:untyped):NimNode =\n      For(preLoop, condition, postLoop, body)\n    discard\n  #[ import atcoder/extra/other/assignment_operator ]#\n  when not declared ATCODER_ASSIGNMENT_OPERATOR_HPP:\n    import std/macros\n    import std/strformat\n    const ATCODER_ASSIGNMENT_OPERATOR_HPP* = 1\n    template `>?=`*(x,y:typed):void = x.max= y\n    template `<?=`*(x,y:typed):void = x.min= y\n    proc `//`*[T:SomeInteger](x,y:T):T = x div y\n    proc `%`*[T:SomeInteger](x,y:T):T = x mod y\n    macro generateAssignmentOperator*(ops:varargs[untyped]) =\n      var strBody = \"\"\n      for op in ops:\n        let op = op.repr\n        var op_raw = op\n        if op_raw[0] == '`':\n          op_raw = op_raw[1..^2]\n        strBody &= fmt\"\"\"proc `{op_raw}=`*[S, T](a:var S, b:T):auto {{.inline discardable.}} = (mixin {op};a = `{op_raw}`(a, b);return a){'\\n'}\"\"\"\n      parseStmt(strBody)\n    generateAssignmentOperator(`mod`, `div`, `and`, `or`, `xor`, `shr`, `shl`, `<<`, `>>`, max, min, `%`, `//`, `&`, `|`, `^`)\n    discard\n  #[ import atcoder/extra/other/inf ]#\n  when not declared ATCODER_INF_HPP:\n    const ATCODER_INF_HPP* = 1\n    template inf*(T:typedesc): untyped = \n      when T is SomeFloat: T(Inf)\n      elif T is SomeInteger: T.high div 2\n      else:\n        static: assert(false)\n    proc `∞`*(T:typedesc):T = T.inf\n    proc `*!`*[T:SomeInteger](a, b:T):T =\n      if a == T(0) or b == T(0): return T(0)\n      var sgn = T(1)\n      if a < T(0): sgn = -sgn\n      if b < T(0): sgn = -sgn\n      let a = abs(a)\n      let b = abs(b)\n      if b > T.inf div a: result = T.inf\n      else: result = min(T.inf, a * b)\n      result *= sgn\n    proc `+!`*[T:SomeInteger](a, b:T):T =\n      result = a + b\n      result = min(T.inf, result)\n      result = max(-T.inf, result)\n    proc `-!`*[T:SomeInteger](a, b:T):T =\n      result = a - b\n      result = min(T.inf, result)\n      result = max(-T.inf, result)\n    discard\n  #[ import atcoder/extra/other/warlus_operator ]#\n  when not declared ATCODER_CHAEMON_WARLUS_OPERATOR_HPP:\n    const ATCODER_CHAEMON_WARLUS_OPERATOR_HPP* = 1\n    import macros\n    proc discardableId*[T](x: T): T {.discardable.} = x\n  \n    proc warlusImpl(x, y:NimNode):NimNode =\n      return quote do:\n        when declaredInScope(`x`):\n          `x` = `y`\n        else:\n          var `x` = `y`\n  \n    macro `:=`*(x, y: untyped): untyped =\n      result = newStmtList()\n      if x.kind == nnkCurly:\n        for i,xi in x: result.add warlusImpl(xi, y)\n      elif x.kind == nnkPar:\n        for i,xi in x: result.add warlusImpl(xi, y[i])\n      else:\n        result.add warlusImpl(x, y)\n        result.add quote do:\n          discardableId(`x`)\n    discard\n  #[ import atcoder/extra/other/seq_array_utils ]#\n  when not declared ATCODER_SEQ_ARRAY_UTILS:\n    const ATCODER_SEQ_ARRAY_UTILS* = 1\n    import std/strformat\n    import std/macros\n    type SeqType = object\n    type ArrayType = object\n    let\n      Seq* = SeqType()\n      Array* = ArrayType()\n  \n    template fill*[T](a:var T, init:untyped) =\n      when T is init.type:\n        a = init\n      else:\n        for x in a.mitems: fill(x, init)\n  \n    template makeSeq*(x:int; init):auto =\n      when init is typedesc: newSeq[init](x)\n      else:\n        var a = newSeq[typeof(init, typeofProc)](x)\n        a.fill(init)\n        a\n  \n    template makeArray*(x:int or Slice[int]; init):auto =\n      var v:array[x, init.type]\n      v\n  \n    macro `[]`*(x:ArrayType or SeqType, args:varargs[untyped]):auto =\n      var a:string\n      if $x == \"Seq\" and args.len == 1 and args[0].kind != nnkExprColonExpr:\n        a = fmt\"newSeq[{args[0].repr}]()\"\n      else:\n        let tail = args[^1]\n        assert tail.kind == nnkExprColonExpr, \"Wrong format of tail\"\n        let\n          args = args[0 .. ^2] & tail[0]\n          init = tail[1]\n        a = fmt\"{init.repr}\"\n        if $x == \"Array\":\n          for i in countdown(args.len - 1, 0): a = fmt\"makeArray({args[i].repr}, {a})\"\n          a = fmt\"{'\\n'}block:{'\\n'}  var a = {a}{'\\n'}  when {init.repr} isnot typedesc:{'\\n'}    a.fill({init.repr}){'\\n'}  a\"\n        elif $x == \"Seq\":\n          for i in countdown(args.len - 1, 0): a = fmt\"makeSeq({args[i].repr}, {a})\"\n          a = fmt\"{'\\n'}block:{'\\n'}  {a}\"\n        else:\n          assert(false)\n      parseStmt(a)\n    discard\n  #[ include atcoder/extra/other/debug ]#\n  when not declared ATCODER_DEBUG_HPP:\n    const ATCODER_DEBUG_HPP* = 1\n    import macros\n    import strformat\n    import terminal\n  \n    macro debugImpl*(n:varargs[untyped]): untyped =\n      #  var a = \"stderr.write \"\n      var a = \"\"\n      a.add \"setForegroundColor fgYellow\\n\"\n      a.add \"stdout.write \"\n  #    a.add \"stderr.write \"\n      for i,x in n:\n        if x.kind == nnkStrLit:\n          a &= fmt\"{x.repr}  \"\n        else:\n          a &= fmt\"\"\" \"{x.repr} = \", {x.repr} \"\"\"\n        if i < n.len - 1:\n          a.add(\"\"\", \", \",\"\"\")\n      a.add(\", \\\"\\\\n\\\"\")\n      a.add \"\\n\"\n      a.add \"resetAttributes()\"\n      parseStmt(a)\n    template debug*(n: varargs[untyped]): untyped =\n      const EVAL =\n        when declared DEBUG: DEBUG\n        else: false\n      when EVAL:\n        debugImpl(n)\n    discard\n  #[ import atcoder/extra/other/solve_proc ]#\n  when not declared ATCODER_SOLVEPROC_HPP:\n    const ATCODER_SOLVEPROC_HPP* = 1\n    import std/macros\n    import std/strformat\n    import std/algorithm\n    import std/sequtils\n    import std/streams\n    import std/strutils\n    import math\n  \n    proc compare_answer_string*(s, t:string, error:float = NaN):bool =\n      if error.classify == fcNaN:\n        return s == t\n      else:\n        var\n          s = s.split(\"\\n\")\n          t = t.split(\"\\n\")\n        if s.len != t.len: return false\n        for i in 0 ..< s.len:\n          var s = s[i].split()\n          var t = t[i].split()\n          if s.len != t.len: return false\n          for j in 0 ..< s.len:\n            if s[j].len == 0:\n              if t[j].len != 0: return false\n            elif t[j].len == 0:\n              return false\n            else:\n              var fs = s[j].parseFloat\n              var ft = t[j].parseFloat\n              if abs(fs - ft) > error and abs(fs - ft) > min(abs(ft), abs(fs)) * error: return false\n        return true\n      doAssert false\n  \n    proc mainBodyHeader():NimNode =\n  #    let macro_def = \"(for s in {x.repr}: (result &= $s;(when output_stdout: stdout.write $s)));(result &= \\\"\\\\n\\\";when output_stdout: stdout.write \\\"\\\\n\\\")\"\n      result = newStmtList()\n      result.add quote(\"@@\") do:\n        mixin echo\n        result = \"\"\n        var resultPointer = result.addr\n        proc echo(x:varargs[string, `$`]) =\n          for s in x:\n            resultPointer[] &= $s\n            when output_stdout: stdout.write $s\n          resultPointer[] &= \"\\n\"\n          when output_stdout: stdout.write \"\\n\"\n  \n    macro solveProc*(head, body:untyped):untyped =\n      var prev_type:NimNode\n      var params:seq[NimNode]\n      for i in countdown(head.len - 1, 1):\n        var identDefs = newNimNode(nnkIdentDefs)\n        if head[i].kind == nnkExprColonExpr:\n          identDefs.add(head[i][0])\n          prev_type = head[i][1]\n        elif head[i].kind == nnkIdent:\n          identDefs.add(head[i])\n        identDefs.add(prev_type)\n        identDefs.add(newEmptyNode())\n        params.add(identDefs)\n      params.add(ident\"auto\")\n      params.reverse()\n      var callparams:seq[NimNode]\n      for i in 1..<params.len:\n        callparams.add(params[i][0])\n  #    var mainBody, naiveBody = mainBodyHeader()\n      var mainBody, checkBody, naiveBody, testBody, generateBody = newStmtList()\n      var hasNaive, hasCheck, hasTest, hasGenerate = false\n      for b in body:\n        if b.kind == nnkCall:\n          if b[0] == ident\"Check\":\n            hasCheck = true\n            var checkStmt = if b.len == 2: b[1] else: b[2]\n            var strmName = if b.len == 2: ident(\"strm\") else: b[1]\n            checkBody.add(newNimNode(nnkWhenStmt).add(\n              newNimNode(nnkElifBranch).add(ident\"DO_CHECK\").add(\n                newBlockStmt(newEmptyNode(), \n                  newStmtList().add(\n                    quote do:\n                      var `strmName` = newStringStream(resultOutput)\n                  ).add(checkStmt)\n            ))))\n          elif b[0] == ident\"Naive\":\n            hasNaive = true\n            naiveBody.add b[1]\n          elif b[0] == ident\"Test\":\n            hasTest = true\n            testBody.add b[1]\n          elif b[0] == ident\"Generate\":\n            hasGenerate = true\n            generateBody.add b[1]\n          else:\n            mainBody.add b\n        else:\n          mainBody.add b\n      mainBody = newStmtList().add(mainBodyHeader()).add(mainBody)\n      #if hasCheck:\n      #  mainBody.add(checkBody)\n      result = newStmtList()\n      let procName = head[0]\n      var discardablePragma = newNimNode(nnkPragma).add(ident(\"discardable\"))\n      var mainParams = params\n      mainParams[0] = ident\"string\"\n  #    var identDefsSub = newNimNode(nnkIdentDefs).add(ident\"output_stdout\").add(newNimNode(nnkBracketExpr).add(ident\"static\").add(ident\"bool\")).add(ident\"true\")\n      var identDefs = newNimNode(nnkIdentDefs).add(ident\"output_stdout\").add(newNimNode(nnkBracketExpr).add(ident\"static\").add(ident\"bool\")).add(ident\"true\")\n      proc copy(a:seq[NimNode]):seq[NimNode] = a.mapIt(it.copy)\n  #    var identDefs = newNimNode(nnkIdentDefs).add(ident\"output_stdout\").add(newNimNode(nnkBracketExpr).add(ident\"static\").add(ident\"bool\")).add(newEmptyNode())\n      mainParams.add(identDefs)\n      #var mainProcDef = newNimNode(nnkProcDef).add(ident\"solve\").add(newEmptyNode()).add(newEmptyNode()).add(newNimNode(nnkFormalParams).add(mainParams.copy())).add(discardablePragma).add(newEmptyNode()).add(newEmptyNode())\n      #result.add(mainProcDef)\n      if hasCheck:\n        result.add(quote do:\n          type CheckResult {.inject.} = ref object of Exception\n            output, err:string\n          template check(b:untyped) =\n            if not b:\n              raise CheckResult(err: b.astToStr, output: resultOutput)\n        )\n      if hasNaive:\n        var naiveProcDef = newNimNode(nnkProcDef).add(ident\"solve_naive\").add(newEmptyNode()).add(newEmptyNode()).add(newNimNode(nnkFormalParams).add(mainParams.copy())).add(discardablePragma).add(newEmptyNode()).add(newEmptyNode())\n        result.add(naiveProcDef)\n  \n      var naiveParams = mainParams.copy()\n      #result.add newProc(name = ident(procName), params = mainParams.copy(), body = mainBody, pragmas = discardablePragma)\n      \n      var mainProcImpl =\n        newStmtList().add(parseStmt(\"mixin echo\")).add quote do:\n        proc solve():string =\n          `mainBody`\n        var resultOutput {.inject.} = solve()\n      var mainTemplateBody = newStmtList().add quote do:\n        `mainProcImpl`\n      if hasCheck:\n        mainTemplateBody.add checkBody\n      mainTemplateBody.add quote do:\n        resultOutput\n      var mainTemplate = quote do:\n        proc `procName`():string {.discardable.} =\n          `mainTemplateBody`\n      mainTemplate[3].add mainParams[1..^1].copy()\n      result.add mainTemplate\n  \n      if hasNaive:\n        let naiveProcName = $procName & \"naive\"\n        naiveBody = mainBodyHeader().add(newBlockStmt(newEmptyNode(), naiveBody))\n        result.add newProc(name = ident(naiveProcName), params = naiveParams, body = naiveBody, pragmas = discardablePragma)\n        var test_body = newStmtList()\n        var var_names = newSeq[string]()\n        for procName in [$procName, $procName & \"_naive\"]:\n          let var_name = \"v\" & procName\n          var_names.add(var_name)\n          var l = newNimNode(nnkCall).add(ident(procName))\n          for c in callparams: l.add(c)\n          l.add(ident\"false\")\n          test_body.add(\n            newNimNode(nnkLetSection).add(\n              newNimNode(nnkIdentDefs).add(ident(var_name)).add(newEmptyNode()).add(l)\n            ))\n        var test_params = params\n        var vars = \"\"\n        for i in 1..<params.len:\n          let p = params[i][0]\n          vars &= &\"  {p.repr} = {{{p.repr}}}\\\\n\"\n        test_params[0] = ident\"bool\"\n  \n        var identDefs = newNimNode(nnkIdentDefs).add(ident\"error\").add(ident\"float\").add(ident(\"NaN\"))\n        test_params.add identDefs\n        test_body.add parseStmt(&\"if not compare_answer_string(vsolve, vsolve_naive, error): echo &\\\"test failed for\\\\n{vars}\\\", \\\"[solve]\\\\n\\\", vsolve, \\\"[solve_naive]\\\\n\\\", vsolve_naive;doAssert false\")\n        result.add newProc(name = ident\"test\", params = test_params, body = test_body, pragmas = discardablePragma)\n      elif hasCheck:\n        var test_body_sub = newStmtList()\n        var var_names = newSeq[string]()\n        for procName in [$procName]:\n          let var_name = \"v\" & procName\n          var_names.add(var_name)\n          var l = newNimNode(nnkCall).add(ident(procName))\n          for c in callparams: l.add(c)\n          l.add(ident\"false\")\n          test_body_sub.add(\n            newNimNode(nnkLetSection).add(\n              newNimNode(nnkIdentDefs).add(ident(var_name)).add(newEmptyNode()).add(l)\n            ))\n        var test_params = params\n        var vars = \"\"\n        for i in 1..<params.len:\n          let p = params[i][0]\n          vars &= &\"  {p.repr} = {{{p.repr}}}\\\\n\"\n        test_params[0] = ident\"bool\"\n        var test_body = newStmtList()\n        var d = &\"try:\\n  {test_body_sub.repr.strip}\\nexcept CheckResult as e:\\n  echo &\\\"check failed for\\\\n{vars}\\\", \\\"[failed statement]\\\\n\\\", e.err.strip, \\\"\\\\n[output]\\\\n\\\", e.output;doAssert false\"\n        test_body.add parseStmt(d)\n        result.add newProc(name = ident\"test\", params = test_params, body = test_body, pragmas = discardablePragma)\n  \n      if hasGenerate:\n        discard\n      if hasTest:\n        discard\n    discard\n\n  when declared USE_DEFAULT_TABLE:\n    when USE_DEFAULT_TABLE:\n      proc `[]`[A, B](self: var Table[A, B], key: A): var B =\n        discard self.hasKeyOrPut(key, B.default)\n        tables_lib.`[]`(self, key)\n\n  # converter toBool[T:ref object](x:T):bool = x != nil\n  # converter toBool[T](x:T):bool = x != T(0)\n  # misc\n  proc `<`[T](a, b:seq[T]):bool =\n    for i in 0 ..< min(a.len, b.len):\n      if a[i] < b[i]: return true\n      elif a[i] > b[i]: return false\n    if a.len < b.len: return true\n    else: return false\n\n  proc ceilDiv*[T:SomeInteger](a, b:T):T =\n    assert b != 0\n    if b < 0: return ceilDiv(-a, -b)\n    result = a.floorDiv(b)\n    if a mod b != 0: result.inc\n\n  template `/^`*[T:SomeInteger](a, b:T):T = ceilDiv(a, b)\n  discard\n"


# see https://github.com/zer0-star/Nim-ACL/tree/master/src/atcoder/convolution.nim
ImportExpand "src/atcoder/convolution.nim" <=== "when not declared ATCODER_CONVOLUTION_HPP:\n  const ATCODER_CONVOLUTION_HPP* = 1\n\n  import std/math\n  import std/sequtils\n  import std/sugar\n  #[ import atcoder/internal_math ]#\n  when not declared ATCODER_INTERNAL_MATH_HPP:\n    const ATCODER_INTERNAL_MATH_HPP* = 1\n    import std/math\n  \n    # Fast moduler by barrett reduction\n    # Reference: https:#en.wikipedia.org/wiki/Barrett_reduction\n    # NOTE: reconsider after Ice Lake\n    type Barrett* = object\n      m*, im:uint\n  \n    # @param m `1 <= m`\n    proc initBarrett*(m:uint):auto = Barrett(m:m, im:(0'u - 1'u) div m + 1)\n  \n    # @return m\n    proc umod*(self: Barrett):uint =\n      self.m\n  \n    {.emit: \"\"\"\n  inline unsigned long long calc_mul(const unsigned long long &a, const unsigned long long &b){\n    return (unsigned long long)(((unsigned __int128)(a)*b) >> 64);\n  }\n  \"\"\".}\n    proc calc_mul*(a,b:culonglong):culonglong {.importcpp: \"calc_mul(#,#)\", nodecl.}\n    # @param a `0 <= a < m`\n    # @param b `0 <= b < m`\n    # @return `a * b % m`\n    proc mul*(self: Barrett, a:uint, b:uint):uint =\n      # [1] m = 1\n      # a = b = im = 0, so okay\n  \n      # [2] m >= 2\n      # im = ceil(2^64 / m)\n      # -> im * m = 2^64 + r (0 <= r < m)\n      # let z = a*b = c*m + d (0 <= c, d < m)\n      # a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im\n      # c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2\n      # ((ab * im) >> 64) == c or c + 1\n      let z = a * b\n      #  #ifdef _MSC_VER\n      #      unsigned long long x;\n      #      _umul128(z, im, &x);\n      #  #else\n      ##TODO\n      #      unsigned long long x =\n      #        (unsigned long long)(((unsigned __int128)(z)*im) >> 64);\n      #  #endif\n      let x = calc_mul(z.culonglong, self.im.culonglong).uint\n      var v = z - x * self.m\n      if self.m <= v: v += self.m\n      return v\n  \n    # @param n `0 <= n`\n    # @param m `1 <= m`\n    # @return `(x ** n) % m`\n    proc pow_mod_constexpr*(x,n,m:int):int =\n      if m == 1: return 0\n      var\n        r = 1\n        y = floorMod(x, m)\n        n = n\n      while n != 0:\n        if (n and 1) != 0: r = (r * y) mod m\n        y = (y * y) mod m\n        n = n shr 1\n      return r.int\n    \n    # Reference:\n    # M. Forisek and J. Jancina,\n    # Fast Primality Testing for Integers That Fit into a Machine Word\n    # @param n `0 <= n`\n    proc is_prime_constexpr*(n:int):bool =\n      if n <= 1: return false\n      if n == 2 or n == 7 or n == 61: return true\n      if n mod 2 == 0: return false\n      var d = n - 1\n      while d mod 2 == 0: d = d div 2\n      for a in [2, 7, 61]:\n        var\n          t = d\n          y = pow_mod_constexpr(a, t, n)\n        while t != n - 1 and y != 1 and y != n - 1:\n          y = y * y mod n\n          t =  t shl 1\n        if y != n - 1 and t mod 2 == 0:\n          return false\n      return true\n    proc is_prime*[n:static[int]]():bool = is_prime_constexpr(n)\n  #  \n  #  # @param b `1 <= b`\n  #  # @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g\n    proc inv_gcd*(a, b:int):(int,int) =\n      var a = floorMod(a, b)\n      if a == 0: return (b, 0)\n    \n      # Contracts:\n      # [1] s - m0 * a = 0 (mod b)\n      # [2] t - m1 * a = 0 (mod b)\n      # [3] s * |m1| + t * |m0| <= b\n      var\n        s = b\n        t = a\n        m0 = 0\n        m1 = 1\n    \n      while t != 0:\n        var u = s div t\n        s -= t * u;\n        m0 -= m1 * u;  # |m1 * u| <= |m1| * s <= b\n    \n        # [3]:\n        # (s - t * u) * |m1| + t * |m0 - m1 * u|\n        # <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)\n        # = s * |m1| + t * |m0| <= b\n    \n        var tmp = s\n        s = t;t = tmp;\n        tmp = m0;m0 = m1;m1 = tmp;\n      # by [3]: |m0| <= b/g\n      # by g != b: |m0| < b/g\n      if m0 < 0: m0 += b div s\n      return (s, m0)\n  \n    # Compile time primitive root\n    # @param m must be prime\n    # @return primitive root (and minimum in now)\n    proc primitive_root_constexpr*(m:int):int =\n      if m == 2: return 1\n      if m == 167772161: return 3\n      if m == 469762049: return 3\n      if m == 754974721: return 11\n      if m == 998244353: return 3\n      var divs:array[20, int]\n      divs[0] = 2\n      var cnt = 1\n      var x = (m - 1) div 2\n      while x mod 2 == 0: x = x div 2\n      var i = 3\n      while i * i <= x:\n        if x mod i == 0:\n          divs[cnt] = i\n          cnt.inc\n          while x mod i == 0:\n            x = x div i\n        i += 2\n      if x > 1:\n        divs[cnt] = x\n        cnt.inc\n      var g = 2\n      while true:\n        var ok = true\n        for i in 0..<cnt:\n          if pow_mod_constexpr(g, (m - 1) div divs[i], m) == 1:\n            ok = false\n            break\n        if ok: return g\n        g.inc\n    proc primitive_root*[m:static[int]]():auto =\n      primitive_root_constexpr(m)\n  \n    # @param n `n < 2^32`\n    # @param m `1 <= m < 2^32`\n    # @return sum_{i=0}^{n-1} floor((ai + b) / m) (mod 2^64)\n    proc floor_sum_unsigned*(n, m, a, b:uint):uint =\n      result = 0\n      var (n, m, a, b) = (n, m, a, b)\n      while true:\n        if a >= m:\n          result += n * (n - 1) div 2 * (a div m)\n          a = a mod m\n        if b >= m:\n          result += n * (b div m)\n          b = b mod m\n  \n        let y_max = a * n + b\n        if y_max < m: break\n        # y_max < m * (n + 1)\n        # floor(y_max / m) <= n\n        n = y_max div m\n        b = y_max mod m\n        swap(m, a)\n    discard\n  #[ import atcoder/internal_bit ]#\n  when not declared ATCODER_INTERNAL_BITOP_HPP:\n    const ATCODER_INTERNAL_BITOP_HPP* = 1\n    import std/bitops\n  \n  #ifdef _MSC_VER\n  #include <intrin.h>\n  #endif\n  \n  # @param n `0 <= n`\n  # @return minimum non-negative `x` s.t. `n <= 2**x`\n    proc ceil_pow2*(n:SomeInteger):int =\n      var x = 0\n      while (1.uint shl x) < n.uint: x.inc\n      return x\n  # @param n `1 <= n`\n  # @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`\n    proc bsf*(n:SomeInteger):int =\n      return countTrailingZeroBits(n)\n    discard\n  #[ import atcoder/element_concepts ]#\n  when not declared ATCODER_ELEMENT_CONCEPTS_HPP:\n    const ATCODER_ELEMENT_CONCEPTS_HPP* = 1\n    proc inv*[T:SomeFloat](a:T):auto = T(1) / a\n    proc init*(self:typedesc[SomeFloat], a:SomeNumber):auto = self(a)\n    type AdditiveGroupElem* = concept x, y, type T\n      x + y\n      x - y\n      -x\n      T(0)\n    type MultiplicativeGroupElem* = concept x, y, type T\n      x * y\n      x / y\n  #    x.inv()\n      T(1)\n    type RingElem* = concept x, y, type T\n      x + y\n      x - y\n      -x\n      x * y\n      T(0)\n      T(1)\n    type FieldElem* = concept x, y, type T\n      x + y\n      x - y\n      x * y\n      x / y\n      -x\n  #    x.inv()\n      T(0)\n      T(1)\n    type FiniteFieldElem* = concept x, type T\n      T is FieldElem\n      T.mod\n      T.mod() is int\n      x.pow(1000000)\n    type hasInf* = concept x, type T\n      T(Inf)\n    discard\n\n\n#  template <class mint,\n#            int g = internal::primitive_root<mint::mod()>,\n#            internal::is_static_modint_t<mint>* = nullptr>\n  type fft_info*[mint:FiniteFieldElem; g, rank2:static[int]] = object\n#    static constexpr int rank2 = bsf_constexpr(mint::mod() - 1);\n    root, iroot: array[rank2 + 1, mint]\n\n    #std::array<mint, rank2 + 1> root;   # root[i]^(2^i) == 1\n    #std::array<mint, rank2 + 1> iroot;  # root[i] * iroot[i] == 1\n    rate2, irate2: array[max(0, rank2 - 2 + 1), mint]\n    #std::array<mint, std::max(0, rank2 - 2 + 1)> rate2;\n    #std::array<mint, std::max(0, rank2 - 2 + 1)> irate2;\n    rate3, irate3: array[max(0, rank2 - 3 + 1), mint]\n  \n    #std::array<mint, std::max(0, rank2 - 3 + 1)> rate3;\n    #std::array<mint, std::max(0, rank2 - 3 + 1)> irate3;\n  \n  proc initFFTInfo*[mint:FiniteFieldElem]():auto =\n    const g = primitive_root[mint.mod]()\n    const rank2 = bsf(mint.mod - 1)\n    var root, iroot:array[rank2 + 1, mint]\n    var rate2, irate2: array[max(0, rank2 - 2 + 1), mint]\n    var rate3, irate3: array[max(0, rank2 - 3 + 1), mint]\n    mixin init, inv\n\n    root[rank2] = mint.init(g).pow((mint.mod - 1) shr rank2)\n    iroot[rank2] = root[rank2].inv()\n    for i in countdown(rank2 - 1, 0):\n      root[i] = root[i + 1] * root[i + 1];\n      iroot[i] = iroot[i + 1] * iroot[i + 1];\n  \n    block:\n      var\n        prod = mint.init(1)\n        iprod = mint.init(1)\n      for i in 0..rank2 - 2:\n        rate2[i] = root[i + 2] * prod\n        irate2[i] = iroot[i + 2] * iprod\n        prod *= iroot[i + 2]\n        iprod *= root[i + 2]\n    block:\n      var\n        prod = mint.init(1)\n        iprod = mint.init(1)\n      for i in 0..rank2 - 3:\n        rate3[i] = root[i + 3] * prod;\n        irate3[i] = iroot[i + 3] * iprod;\n        prod *= iroot[i + 3];\n        iprod *= root[i + 3];\n    return fft_info[mint, g, rank2](root:root, iroot:iroot, rate2:rate2, irate2:irate2, rate3: rate3, irate3:irate3)\n  \n  proc butterfly*[mint:FiniteFieldElem](a:var seq[mint]) =\n    mixin init\n    let n = a.len\n    let h = ceil_pow2(n)\n\n    const info = initFFTInfo[mint]()\n\n    var len = 0  # a[i, i+(n>>len), i+2*(n>>len), ..] is transformed\n    while len < h:\n      if h - len == 1:\n        let p = 1 shl (h - len - 1)\n        var rot = mint.init(1)\n        for s in 0..<(1 shl len):\n          var offset = s shl (h - len)\n          for i in 0..<p:\n            let l = a[i + offset]\n            let r = a[i + offset + p] * rot\n            a[i + offset] = l + r\n            a[i + offset + p] = l - r\n          if s + 1 != (1 shl len):\n            rot *= info.rate2[bsf(not s.uint)]\n        len.inc\n      else:\n        # 4-base\n        let p = 1 shl (h - len - 2)\n        var\n          rot = mint.init(1)\n          imag = info.root[2]\n        for s in 0..<(1 shl len):\n          let\n            rot2 = rot * rot\n            rot3 = rot2 * rot\n            offset = s shl (h - len)\n          for i in 0..<p:\n            let\n              mod2 = (mint.mod() * mint.mod()).uint\n              a0 = (a[i + offset].val()).uint\n              a1 = (a[i + offset + p].val() * rot.val()).uint\n              a2 = (a[i + offset + 2 * p].val() * rot2.val()).uint\n              a3 = (a[i + offset + 3 * p].val() * rot3.val()).uint\n              a1na3imag = (mint.init(a1 + mod2 - a3).val() * imag.val()).uint\n              na2 = mod2 - a2\n            a[i + offset] = mint.init(a0 + a2 + a1 + a3)\n            a[i + offset + 1 * p] = mint.init(a0 + a2 + (2.uint * mod2 - (a1 + a3)))\n            a[i + offset + 2 * p] = mint.init(a0 + na2 + a1na3imag)\n            a[i + offset + 3 * p] = mint.init(a0 + na2 + (mod2 - a1na3imag))\n          if s + 1 != (1 shl len):\n            rot *= info.rate3[bsf(not s.uint)]\n        len += 2\n  \n  proc butterfly_inv*[mint:FiniteFieldElem](a:var seq[mint]) =\n    let n = a.len\n    let h = ceilpow2(n)\n    mixin init\n\n    const info = initFFTInfo[mint]()\n  \n    var len = h;  # a[i, i+(n>>len), i+2*(n>>len), ..] is transformed\n    while len > 0:\n      if len == 1:\n        let p = 1 shl (h - len)\n        var irot = mint.init(1)\n        for s in 0..<(1 shl (len - 1)):\n          let offset = s shl (h - len + 1)\n          for i in 0..<p:\n            let\n              l = a[i + offset]\n              r = a[i + offset + p]\n            a[i + offset] = l + r\n            a[i + offset + p] = mint.init((mint.mod() + l.val() - r.val()) * irot.val())\n          if s + 1 != (1 shl (len - 1)):\n            irot *= info.irate2[bsf(not s.uint)]\n        len.dec\n      else:\n        # 4-base\n        let p = 1 shl (h - len);\n        var irot = mint.init(1)\n        let iimag = info.iroot[2]\n        for s in 0..<(1 shl (len - 2)):\n          let\n            irot2 = irot * irot\n            irot3 = irot2 * irot\n            offset = s shl (h - len + 2)\n          for i in 0..<p:\n            let\n              a0 = a[i + offset + 0 * p].val().uint\n              a1 = a[i + offset + 1 * p].val().uint\n              a2 = a[i + offset + 2 * p].val().uint\n              a3 = a[i + offset + 3 * p].val().uint\n              a2na3iimag = mint.init((mint.mod.uint + a2 - a3) * iimag.val().uint).val().uint\n  \n            a[i + offset] = mint.init(a0 + a1 + a2 + a3)\n            a[i + offset + 1 * p] = mint.init((a0 + (mint.mod().uint - a1) + a2na3iimag) * irot.val().uint)\n            a[i + offset + 2 * p] = mint.init((a0 + a1 + (mint.mod().uint - a2) + (mint.mod().uint - a3)) * irot2.val().uint)\n            a[i + offset + 3 * p] = mint.init((a0 + (mint.mod().uint - a1) + (mint.mod().uint - a2na3iimag)) * irot3.val().uint)\n          if s + 1 != (1 shl (len - 2)):\n            irot *= info.irate3[bsf(not s.uint)]\n        len -= 2\n\n  proc convolution_naive*[mint:FiniteFieldElem](a, b:seq[mint]):seq[mint] =\n    mixin `+=`\n    let (n, m) = (a.len, b.len)\n    result = newSeq[mint](n + m - 1)\n#    result = newSeqWith(n + m - 1, mint(0))\n    if n < m:\n      for j in 0..<m:\n        for i in 0..<n:\n          result[i + j] += a[i] * b[j]\n    else:\n      for i in 0..<n:\n        for j in 0..<m:\n          result[i + j] += a[i] * b[j]\n\n  proc convolution_fft*[mint:FiniteFieldElem](a, b:seq[mint]):seq[mint] =\n    mixin init, inv\n    let\n      (n, m) = (a.len, b.len)\n      z = 1 shl ceil_pow2(n + m - 1)\n    var (a, b) = (a, b)\n    a.setLen(z)\n    butterfly(a)\n    b.setLen(z)\n    butterfly(b)\n    for i in 0..<z:\n      a[i] *= b[i];\n    butterfly_inv(a)\n    a.setLen(n + m - 1)\n    let iz = mint.init(z).inv()\n    for i in 0..<n + m - 1: a[i] *= iz\n    return a\n\n  proc convolution*[mint:FiniteFieldElem](a, b:seq[mint]):seq[mint] =\n    let (n, m) = (a.len, b.len)\n    if n == 0 or m == 0: return\n    if min(n, m) <= 60: return convolution_naive(a, b)\n    return convolution_fft(a, b)\n  \n#  template <class mint, internal::is_static_modint_t<mint>* = nullptr>\n#  std::vector<mint> convolution(const std::vector<mint>& a,\n#                                const std::vector<mint>& b) {\n#    int n = int(a.size()), m = int(b.size());\n#    if (!n || !m) return {};\n#    if (std::min(n, m) <= 60) return convolution_naive(a, b);\n#    return internal::convolution_fft(a, b);\n#  }\n\n\n  #[ import atcoder/modint ]#\n  when not declared ATCODER_MODINT_HPP:\n    const ATCODER_MODINT_HPP* = 1\n    import std/macros\n    #[ import atcoder/generate_definitions ]#\n    when not declared ATCODER_GENERATE_DEFINITIONS_NIM:\n      const ATCODER_GENERATE_DEFINITIONS_NIM* = 1\n      import std/macros\n    \n      type hasInv* = concept x\n        var t: x\n        t.inv()\n    \n      template generateDefinitions*(name, l, r, typeObj, typeBase, body: untyped): untyped {.dirty.} =\n        proc name*(l, r: typeObj): auto {.inline.} =\n          type T = l.type\n          body\n        proc name*(l: typeBase; r: typeObj): auto {.inline.} =\n          type T = r.type\n          body\n        proc name*(l: typeObj; r: typeBase): auto {.inline.} =\n          type T = l.type\n          body\n    \n      template generatePow*(name) {.dirty.} =\n        proc pow*(m: name; p: SomeInteger): name {.inline.} =\n          when name is hasInv:\n            if p < 0: return pow(m.inv(), -p)\n          else:\n            assert p >= 0\n          if (p.type)(0) <= p:\n            var\n              p = p.uint\n              m = m\n            result = m.unit()\n            while p > 0'u:\n              if (p and 1'u) != 0'u: result *= m\n              m *= m\n              p = p shr 1'u\n        proc `^`*[T:name](m: T; p: SomeInteger): T {.inline.} = m.pow(p)\n    \n      macro generateConverter*(name, from_type, to_type) =\n        let fname = ident(\"to\" & $`name` & \"OfGenerateConverter\")\n        quote do:\n          type `name`* = `to_type`\n          converter `fname`*(a:`from_type`):`name` {.used.} =\n            `name`.init(a)\n      discard\n  \n    type\n      StaticModInt*[M: static[int]] = object\n        a:uint32\n      DynamicModInt*[T: static[int]] = object\n        a:uint32\n  \n    type ModInt* = StaticModInt or DynamicModInt\n  #  type ModInt* = concept x, type T\n  #    T is StaticModInt or T is DynamicModInt\n  \n    proc isStaticModInt*(T:typedesc):bool = T is StaticModInt\n    proc isDynamicModInt*(T:typedesc):bool = T is DynamicModInt\n    proc isModInt*(T:typedesc):bool = T.isStaticModInt or T.isDynamicModInt\n    proc isStatic*(T:typedesc[ModInt]):bool = T is StaticModInt\n  \n    #[ import atcoder/internal_math ]#\n  \n    proc getBarrett*[T:static[int]](t:typedesc[DynamicModInt[T]]):ptr Barrett =\n      var Barrett_of_DynamicModInt {.global.} = initBarrett(998244353.uint)\n      return Barrett_of_DynamicModInt.addr\n    proc getMod*[T:static[int]](t:typedesc[DynamicModInt[T]]):uint32 {.inline.} =\n      (t.getBarrett)[].m.uint32\n    proc setMod*[T:static[int]](t:typedesc[DynamicModInt[T]], M:SomeInteger){.inline.} =\n      (t.getBarrett)[] = initBarrett(M.uint)\n  \n    proc `$`*(m: StaticModInt or DynamicModInt): string {.inline.} = $(m.val())\n  \n    template umod*[T:ModInt](self: typedesc[T] or T):uint32 =\n      when T is typedesc:\n        when T is StaticModInt:\n          T.M.uint32\n        elif T is DynamicModInt:\n          T.getMod()\n        else:\n          static: assert false\n      else: T.umod\n  \n    template `mod`*[T:ModInt](self:typedesc[T] or T):int = T.umod.int\n  \n    proc init*[T:ModInt](t:typedesc[T], v: SomeInteger or T): auto {.inline.} =\n      when v is T: return v\n      else:\n        when v is SomeUnsignedInt:\n          if v.uint < T.umod:\n            return T(a:v.uint32)\n          else:\n            return T(a:(v.uint mod T.umod.uint).uint32)\n        else:\n          var v = v.int\n          if 0 <= v:\n            if v < T.mod: return T(a:v.uint32)\n            else: return T(a:(v mod T.mod).uint32)\n          else:\n            v = v mod T.mod\n            if v < 0: v += T.mod\n            return T(a:v.uint32)\n    proc unit*[T:ModInt](t:typedesc[T] or T):T = T.init(1)\n  \n    template initModInt*(v: SomeInteger or ModInt; M: static[int] = 1_000_000_007): auto =\n      StaticModInt[M].init(v)\n  \n  # TODO\n  #  converter toModInt[M:static[int]](n:SomeInteger):StaticModInt[M] {.inline.} = initModInt(n, M)\n  \n  #  proc initModIntRaw*(v: SomeInteger; M: static[int] = 1_000_000_007): auto {.inline.} =\n  #    ModInt[M](v.uint32)\n    proc raw*[T:ModInt](t:typedesc[T], v:SomeInteger):auto = T(a:v)\n  \n    proc inv*[T:ModInt](v:T):T {.inline.} =\n      var\n        a = v.a.int\n        b = T.mod\n        u = 1\n        v = 0\n      while b > 0:\n        let t = a div b\n        a -= t * b;swap(a, b)\n        u -= t * v;swap(u, v)\n      return T.init(u)\n  \n    proc val*(m: ModInt): int {.inline.} = int(m.a)\n    converter toInt*(m: ModInt):int {.inline.} = m.val\n  \n    proc `-`*[T:ModInt](m: T): T {.inline.} =\n      if int(m.a) == 0: return m\n      else: return T(a:m.umod() - m.a)\n  \n    proc `+=`*[T:ModInt](m: var T; n: SomeInteger | T) {.inline.} =\n      m.a += T.init(n).a\n      if m.a >= T.umod: m.a -= T.umod\n  \n    proc `-=`*[T:ModInt](m: var T; n: SomeInteger | T) {.inline.} =\n      m.a -= T.init(n).a\n      if m.a >= T.umod: m.a += T.umod\n  \n    proc `*=`*[T:ModInt](m: var T; n: SomeInteger | T) {.inline.} =\n      when T is StaticModInt:\n        m.a = (m.a.uint * T.init(n).a.uint mod T.umod).uint32\n      elif T is DynamicModInt:\n        m.a = T.getBarrett[].mul(m.a.uint, T.init(n).a.uint).uint32\n      else:\n        static: assert false\n  \n    proc `/=`*[T:ModInt](m: var T; n: SomeInteger | T) {.inline.} =\n      m.a = (m.a.uint * T.init(n).inv().a.uint mod T.umod).uint32\n  \n    generateDefinitions(`+`, m, n, ModInt, SomeInteger):\n      result = T.init(m)\n      result += n\n  \n    generateDefinitions(`-`, m, n, ModInt, SomeInteger):\n      result = T.init(m)\n      result -= n\n  \n    generateDefinitions(`*`, m, n, ModInt, SomeInteger):\n      result = T.init(m)\n      result *= n\n  \n    generateDefinitions(`/`, m, n, ModInt, SomeInteger):\n      result = T.init(m)\n      result /= n\n  \n    generateDefinitions(`==`, m, n, ModInt, SomeInteger):\n      result = (T.init(m).val() == T.init(n).val())\n  \n    proc inc*(m: var ModInt) {.inline.} =\n      m.a.inc\n      if m.a == m.umod.uint32:\n        m.a = 0\n  \n    proc dec*(m: var ModInt) {.inline.} =\n      if m.a == 0.uint32:\n        m.a = m.umod - 1\n      else:\n        m.a.dec\n  \n    generatePow(ModInt)\n  \n    template useStaticModint*(name, M) =\n      generateConverter(name, int, StaticModInt[M])\n    template useDynamicModInt*(name, M) =\n      generateConverter(name, int, DynamicModInt[M])\n  \n    useStaticModInt(modint998244353, 998244353)\n    useStaticModInt(modint1000000007, 1000000007)\n    useDynamicModInt(modint, -1)\n    discard\n#  template <unsigned int mod = 998244353,\n#      class T,\n#      std::enable_if_t<internal::is_integral<T>::value>* = nullptr>\n  proc convolution*[T:SomeInteger](a, b:seq[T], M:static[uint] = 998244353):seq[T] =\n    let (n, m) = (a.len, b.len)\n    if n == 0 or m == 0: return newSeq[T]()\n  \n    type mint = StaticModInt[M.int]\n    static:\n      assert mint is FiniteFieldElem\n    return convolution(\n      a.map((x:T) => mint.init(x)), \n      b.map((x:T) => mint.init(x))\n    ).map((x:mint) => T(x.val()))\n\n  proc convolution_ll*(a, b:seq[int]):seq[int] =\n    let (n, m) = (a.len, b.len)\n    if n == 0 or m == 0: return newSeq[int]()\n    const\n      MOD1:uint = 754974721  # 2^24\n      MOD2:uint = 167772161  # 2^25\n      MOD3:uint = 469762049  # 2^26\n      M2M3 = MOD2 * MOD3\n      M1M3 = MOD1 * MOD3\n      M1M2 = MOD1 * MOD2\n      M1M2M3 = MOD1 * MOD2 * MOD3\n\n      i1 = inv_gcd((MOD2 * MOD3).int, MOD1.int)[1].uint\n      i2 = inv_gcd((MOD1 * MOD3).int, MOD2.int)[1].uint\n      i3 = inv_gcd((MOD1 * MOD2).int, MOD3.int)[1].uint\n    \n    let\n      c1 = convolution(a, b, MOD1)\n      c2 = convolution(a, b, MOD2)\n      c3 = convolution(a, b, MOD3)\n  \n    var c = newSeq[int](n + m - 1)\n    for i in 0..<n + m - 1:\n      var x = 0.uint\n      x += (c1[i].uint * i1) mod MOD1 * M2M3\n      x += (c2[i].uint * i2) mod MOD2 * M1M3\n      x += (c3[i].uint * i3) mod MOD3 * M1M2\n      # B = 2^63, -B <= x, r(real value) < B\n      # (x, x - M, x - 2M, or x - 3M) = r (mod 2B)\n      # r = c1[i] (mod MOD1)\n      # focus on MOD1\n      # r = x, x - M', x - 2M', x - 3M' (M' = M % 2^64) (mod 2B)\n      # r = x,\n      #   x - M' + (0 or 2B),\n      #   x - 2M' + (0, 2B or 4B),\n      #   x - 3M' + (0, 2B, 4B or 6B) (without mod!)\n      # (r - x) = 0, (0)\n      #       - M' + (0 or 2B), (1)\n      #       -2M' + (0 or 2B or 4B), (2)\n      #       -3M' + (0 or 2B or 4B or 6B) (3) (mod MOD1)\n      # we checked that\n      #   ((1) mod MOD1) mod 5 = 2\n      #   ((2) mod MOD1) mod 5 = 3\n      #   ((3) mod MOD1) mod 5 = 4\n#      var diff = c1[i] - floorMod(x.int, MOD1.int)\n      var diff = c1[i] - floorMod(cast[int](x), MOD1.int)\n      if diff < 0: diff += MOD1.int\n      const offset = [0'u, 0'u, M1M2M3, 2'u * M1M2M3, 3'u * M1M2M3]\n      x -= offset[diff mod 5]\n      c[i] = cast[int](x)\n    return c\n  discard\n"

# see https://github.com/zer0-star/Nim-ACL/tree/master/src/atcoder/modint.nim
ImportExpand "src/atcoder/modint.nim" <=== ""

# see https://github.com/zer0-star/Nim-ACL/tree/master/src/atcoder/extra/math/combination.nim
ImportExpand "src/lib/math/combination.nim" <=== "when not defined ATCODER_COMBINATION_HPP:\n  const ATCODER_COMBINATION_HPP* = 1\n  #[ import atcoder/element_concepts ]#\n\n  type Combination*[T] = object\n    fact_a, rfact_a: seq[T]\n\n  type CombinationC* = concept x\n    x is typedesc[FieldElem] or x is var Combination\n\n  proc enhance[T:FieldElem](cmb: var Combination[T], k:int):auto =\n    if k >= cmb.fact_a.len:\n      if cmb.fact_a.len == 0:\n        cmb.fact_a = @[T(1)]\n        cmb.rfact_a = @[T(1)]\n      let sz_old = cmb.fact_a.len - 1\n      let sz = max(sz_old * 2, k)\n      cmb.fact_a.setlen(sz + 1)\n      cmb.rfact_a.setlen(sz + 1)\n      for i in sz_old + 1..sz: cmb.fact_a[i] = cmb.fact_a[i-1] * T(i)\n      cmb.rfact_a[sz] = T(1) / cmb.fact_a[sz]\n      for i in countdown(sz - 1, sz_old + 1): cmb.rfact_a[i] = cmb.rfact_a[i + 1] * T(i + 1)\n    return cmb.addr\n\n  proc enhance(T:typedesc[FieldElem], k:int):auto {.discardable.} =\n    var cmb{.global.} = Combination[T]()\n    return cmb.enhance(k)\n\n  template zero*(T:typedesc[FieldElem]):T = T(0)\n  template zero*[T:FieldElem](cmb:Combination[T]):T = T(0)\n  \n  template fact*(T:CombinationC, k:int):auto = T.enhance(k)[].fact_a[k]\n  template rfact*(T:CombinationC, k:int):auto = T.enhance(k)[].rfact_a[k]\n  template inv*(T:CombinationC, k:int):auto = T.fact(k - 1) * T.rfact(k)\n\n  template resetCombination*(T:typedesc[FieldElem] or var Combination) =\n    var p = T.enhance(-1)\n    p[].fact_a.setLen(0)\n    p[].rfact_a.setLen(0)\n\n  template P*(T:CombinationC, n,r:int):auto =\n    if r < 0 or n < r: T.zero()\n    else: T.fact(n) * T.rfact(n - r)\n  template C_impl*(T:CombinationC, n, r:int):auto =\n    if r < 0 or n < r: T.zero()\n    else: T.fact(n) * T.rfact(r) * T.rfact(n - r)\n  template C*(T:CombinationC, n,r:int):auto =\n    if n >= 0:\n      T.C_impl(n, r)\n    else:\n      let N = -n\n      var a = T.C_impl(N + r - 1, N - 1)\n      if r mod 2 != 0: a *= -1\n      a\n  template H*(T:CombinationC, n,r:int):auto =\n    if n < 0 or r < 0: T.zero()\n    elif r == 0: T.zero() + 1\n    else: T.C(n + r - 1, r)\n  template P_large*(T:CombinationC, n,r:int):auto =\n    if r < 0 or n < r: T.zero()\n    else:\n      var a = T(1)\n      for i in 0..<r:a *= n - i\n      a\n  template C_large_impl*(T:CombinationC, n,r:int):auto =\n    if r < 0 or n < r: T.zero()\n    else: T.P_large(n, r) * T.rfact(r)\n  template C_large*(T:CombinationC, n,r:int):auto =\n    if n >= 0:\n      T.C_large_impl(n, r)\n    else:\n      let N = -n\n      var a = T.C_large_impl(N + r - 1, N - 1)\n      if r mod 2 != 0: a *= -1\n      a\n  template H_large*(T:CombinationC, n,r:int):auto =\n    if n < 0 or r < 0: T.zero()\n    elif r == 0: T.zero() + 1\n    else: T.C_large(n + r - 1, r)\n  discard\n"


type mint = modint998244353

const DO_TEST = false

proc get(N, x, y:int, alpha, beta:mint):seq[mint] =
  # 確率alpha, betaでN回目の移動の試行で(x, y)で出会う確率(実際には2人いるので2N回の試行となる)
  # resultはインデックス0..Nをとり、インデックスiにはi回目の移動で出会う確率が入る
  var l, r = newSeq[mint](N + 1)
  for i in 0..N:
    if i - x < 0 or (i + x) mod 2 != 0:
      l[i] = 0
    else:
      l[i] = mint.rfact((i + x) div 2) * mint.rfact((i - x) div 2) * alpha^i
    if i - y < 0 or (i + y) mod 2 != 0:
      r[i] = 0
    else:
      r[i] = mint.rfact((i + y) div 2) * mint.rfact((i - y) div 2) * beta^i
  result = convolution(l, r)[0..N]
  for i in 0 ..< result.len:
    result[i] *= mint.fact(i)

when not DO_TEST:
  let
    N = nextInt()
    x0, y0, x1, y1 = nextInt()
    A, B = nextInt()
    a = @[0] & newSeqWith(N, nextInt())
    x = abs(x0 - x1)
    y = abs(y0 - y1)
    alpha = mint(A) / mint(2 * (A + B))
    beta = mint(B) / mint(2 * (A + B))
  # 制約を満たすかテスト
  block test:
    doAssert N in 1 .. 10^5
    doAssert x0 in 0 .. 10^9
    doAssert y0 in 0 .. 10^9
    doAssert x1 in 0 .. 10^9
    doAssert y1 in 0 .. 10^9
    doAssert (x0, y0) != (x1, y1)
    doAssert A in 1 .. 10^6
    doAssert B in 1 .. 10^6
    for i in 1..N:
      doAssert a[i] in 1 .. 10^9
  var
    dp = get(N * 2 + 1, x, y, alpha, beta)
    dp0 = get(N * 2 + 1, 0, 0, alpha, beta)
  proc calc(l, r:int) =
    d := r - l
    if d > 1:
      m := (l + r) div 2
      # l ..< mを計算する
      calc(l, m)
      # dp[l..<m]をdp[m..<r]に伝搬する
      c := dp[l ..< m].convolution(dp0[0..<d])
      for i in m ..< r:
        dp[i] -= c[i - l]
      # m ..< rを計算する
      calc(m, r)
  calc(0, N * 2 + 1)
  var ans = mint(0)
  for i in 1..N:
    ans += a[i] * dp[i * 2]
  echo ans
#else:
#  # テスト用
#  proc estimateRational(a:mint, ub:int):(int, int) =
#    for d in 1..ub:
#      var n = (a * d).val
#      if n <= ub:
#        return (n, d)
#    echo "estimate failed"
#    return (-1, -1)
#
#  var
#    alpha = mint(1) / mint(2)
#    beta = mint(1) / mint(2)
#  const D = 100
#  proc naive(n:int):array[-D..D, array[-D..D, mint]] =
#    for x in -D..D:
#      for y in -D..D:
#        result[x][y] = mint(0)
#    result[0][0] = 1
#    for t in n:
#      var result2:array[-D..D, array[-D..D, mint]]
#      for x in -D..D:
#        for y in -D..D:
#          if x + 1 <= D:
#            result2[x + 1][y] += result[x][y] * alpha
#          if x - 1 >= -D:
#            result2[x - 1][y] += result[x][y] * alpha
#          if y + 1 <= D:
#            result2[x][y + 1] += result[x][y] * beta
#          if y - 1 >= -D:
#            result2[x][y - 1] += result[x][y] * beta
#      swap result, result2
#
#  var
#    x = 3
#    y = 4
#  var a0 = get(20, x, y, alpha, beta)
#
#  for i, a in a0:
#    var dp = naive(i)
#    echo i, " ", a, " ", estimateRational(a, 10000), " ", dp[x][y]
#