import algorithm, complex, macros, math, sequtils, sets, strformat, strutils, sugar, tables macro unpack*(rhs: seq, cnt: static[int]): auto = let v = genSym(); result = quote do:(let `v` = `rhs`;()) for i in 0 ..< cnt: result[1].add(quote do:`v`[`i`]) template input*(T: typedesc, cnt: Natural = 1): untyped = let line = stdin.readLine.split(" ") when T is int: line.map(parseInt).unpack(cnt) elif T is float: line.map(parseFloat).unpack(cnt) elif T is string: line.unpack(cnt) elif T is char: line.mapIt(it[0]).unpack(cnt) elif T is seq[int]: line.map(parseint) elif T is seq[float]: line.map(parseFloat) elif T is seq[string]: line elif T is seq[char]: line.mapIt(it[0]) proc `|=`*(n: var int, m: int) = n = n or m proc `|=`*(n: var bool, m: bool) = n = n or m proc `&=`*(n: var int, m: int) = n = n and m proc `&=`*(n: var bool, m: bool) = n = n and m proc `^=`*(n: var int, m: int) = n = n xor m proc `^=`*(n: var bool, m: bool) = n = n xor m proc `%=`*(n: var int, m: int) = n = n mod m proc `/=`*(n: var int, m: int) = n = n div m proc `<<=`*(n: var int, m: int) = n = n shl m proc `>>=`*(n: var int, m: int) = n = n shr m proc `?=`*(n: var SomeNumber, m: SomeNumber) = n = max(n, m) proc newSeq2*[T](n1, n2: Natural): seq[seq[T]] = newSeqWith(n1, newSeq[T](n2)) proc newSeq3*[T](n1, n2, n3: Natural): seq[seq[seq[T]]] = newSeqWith(n1, newSeqWith(n2, newSeq[T](n3))) # -------------------------------------------------- # const modulus = 10 ^ 9 + 7 type ModInt* = object v: int proc initModInt*(n: int): ModInt = result.v = (n mod modulus + modulus) mod modulus proc `$`*(x: ModInt): string = $x.v proc pow*(x: ModInt, n: int): ModInt = if n < 0: return pow(x, -n).pow(modulus - 2) var p = 1 var x = x.v var n = n while n > 0: if (n and 1) != 0: p = p * x mod modulus x = x * x mod modulus n = n shr 1 result.v = p proc inverse*(x: ModInt): ModInt = pow(x, modulus - 2) proc `+`*(x: ModInt): ModInt = result.v = x.v proc `-`*(x: ModInt): ModInt = result.v = modulus - x.v if result.v == modulus: result.v = 0 proc `+`*(a: ModInt, b: ModInt): ModInt = result.v = a.v + b.v if result.v >= modulus: result.v -= modulus proc `-`*(a: ModInt, b: ModInt): ModInt = result.v = a.v - b.v if result.v < 0: result.v += modulus proc `*`*(a: ModInt, b: ModInt): ModInt = result.v = a.v * b.v if result.v >= modulus: result.v = result.v mod modulus proc `/`*(a: ModInt, b: ModInt): ModInt = result.v = a.v * b.inverse().v if result.v >= modulus: result.v = result.v mod modulus proc `+`*(a: ModInt, b: int): ModInt = a + initModInt(b) proc `-`*(a: ModInt, b: int): ModInt = a - initModInt(b) proc `*`*(a: ModInt, b: int): ModInt = a * initModInt(b) proc `/`*(a: ModInt, b: int): ModInt = a / initModInt(b) proc `+`*(a: int, b: ModInt): ModInt = initModInt(a) + b proc `-`*(a: int, b: ModInt): ModInt = initModInt(a) - b proc `*`*(a: int, b: ModInt): ModInt = initModInt(a) * b proc `/`*(a: int, b: ModInt): ModInt = initModInt(a) / b proc `+=`*(a: var ModInt; b: ModInt) = a = a + b proc `-=`*(a: var ModInt; b: ModInt) = a = a - b proc `*=`*(a: var ModInt; b: ModInt) = a = a * b proc `/=`*(a: var ModInt; b: ModInt) = a = a / b proc `+=`*(a: var ModInt; b: int) = a = a + b proc `-=`*(a: var ModInt; b: int) = a = a - b proc `*=`*(a: var ModInt; b: int) = a = a * b proc `/=`*(a: var ModInt; b: int) = a = a / b # -------------------------------------------------- # let (N, p) = input(int, 2) var A = newSeq[ModInt](N + 1) A[1] = initModInt(0) A[2] = initModInt(1) for i in 3 .. N: A[i] += p * A[i - 1] A[i] += A[i - 2] var cum = newSeq[ModInt](N + 2) for i in countdown(N, 1): cum[i] = cum[i + 1] + A[i] var res = initModInt(0) for i in 1 .. N: res += A[i] * cum[i] echo res