import sequtils,math proc getchar_unlocked():char {. importc:"getchar_unlocked",header: "" .} type ModInt = object v:int # 0~MODに収まる const MOD = 129402307 template useModulo() = proc toModInt*(a:int) : ModInt = if a < -MOD : result.v = ((a mod MOD) + MOD) mod MOD elif a < 0 : result.v = a + MOD elif a >= MOD: result.v = a mod MOD else: result.v = a proc `+`*(a,b:ModInt) : ModInt = result.v = a.v + b.v if result.v >= MOD : result.v = result.v mod MOD proc `*`*(a,b:ModInt) : ModInt = result.v = a.v * b.v if result.v >= MOD : result.v = result.v mod MOD proc `^`*(a:ModInt,b:int) : ModInt = if a.v == 0 : return 0.toModInt() if b == 0 : return 1.toModInt() if b == 1 : return a let pow = a^(b div 2) if b mod 2 == 0 : return pow * pow return pow * pow * a proc `+`*(a:int,b:ModInt) : ModInt = a.toModInt() + b proc `+`*(a:ModInt,b:int) : ModInt = a + b.toModInt() proc `-`*(a:ModInt,b:int) : ModInt = a + (-b) proc `-`*(a,b:ModInt) : ModInt = a + (-b.v) proc `-`*(a:int,b:ModInt) : ModInt = a.toModInt() + (-b.v) proc `*`*(a:int,b:ModInt) : ModInt = a.toModInt() * b proc `*`*(a:ModInt,b:int) : ModInt = a * b.toModInt() proc `/`*(a,b:ModInt) : ModInt = a * b^(MOD-2) proc `$`*(a:ModInt) : string = $a.v useModulo() proc scan(isTrulyZero:var bool): ModInt = result = 0.toModInt() block: let k = getchar_unlocked() result = 10 * result + k.ord - '0'.ord isTrulyZero = k == '0' block: let k = getchar_unlocked() if k < '0': return isTrulyZero = false result = 10 * result + k.ord - '0'.ord while true: let k = getchar_unlocked() if k < '0': return result = 10 * result + k.ord - '0'.ord proc scanX(): int = const nowMOD = MOD - 1 result = 0 while true: let k = getchar_unlocked() if k < '0': break result = 10 * result + k.ord - '0'.ord if result >= nowMOD : result = result mod nowMOD var isTrulyZero = false let n = scan(isTrulyZero) let m = scanX() if n.v == 0 : if isTrulyZero : echo 0 elif m == 0: echo 1 else: echo 0 else:echo n^m