#include <iostream>
using namespace std;
int main() {
    long long m, x = 2;
    cin >> m;
    for (int i = 0; i < 1000000; i++) x = (x * x + 1) % m;
    cout << x << "\n";
}

#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>
using boost::multiprecision::cpp_int;
using namespace std;
int main() {
    cpp_int m, x = 2;
    cin >> m;
    for (int i = 0; i < 1000000; i++) x = (x * x + 1) % m;
    cout << x << "\n";
}

#include <iostream>
#include <string>
using namespace std;
__extension__ typedef __int128 i128;
string str(i128 v) {
    if (v == 0) return "0";
    string s;
    while (v > 0) {
        s.insert(s.begin(), char('0' + int(v % 10)));
        v /= 10;
    }
    return s;
}
int main() {
    string s;
    cin >> s;
    i128 n = 0, a = 1;
    for (char c : s) n = n * 10 + (c - '0');
    for (int i = 0; i < 126; i++) a = a * 2 + 1;
    i128 b = n * 1000000;
    cout << str(a) << "\n" << str(b / 7) << "\n" << str(b % 1000000007) << "\n" << str(n) << "\n";
    i128 m = n / 1000000 + 9, x = 2;
    for (int i = 0; i < 1000000; i++) x = (x * x + 1) % m;
    cout << str(x) << "\n";
}

#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>
using boost::multiprecision::int128_t;
using namespace std;
int main() {
    int128_t n, a = 1;
    cin >> n;
    for (int i = 0; i < 126; i++) a = a * 2 + 1;
    int128_t b = n * 1000000;
    cout << a << "\n" << b / 7 << "\n" << b % 1000000007 << "\n" << n << "\n";
    int128_t m = n / 1000000 + 9, x = 2;
    for (int i = 0; i < 1000000; i++) x = (x * x + 1) % m;
    cout << x << "\n";
}

#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>
using boost::multiprecision::cpp_int;
using namespace std;
int main() {
    cpp_int n, f = 1;
    cin >> n;
    for (int i = 1; i <= 200; i++) f *= i;
    cpp_int m = n / 1000000 + 9;
    cpp_int x = 2;
    for (int i = 0; i < 1000000; i++) x = (x * x + 1) % m;
    cout << f << "\n" << f / n << "\n" << x << "\n";
}

{
    long long m;
    cin >> m;
    long long x = 2;
    for (int i = 0; i < 1000000; i++) x = (x * x + 1) % m;
    cout << x << "\n";
}

#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>
using boost::multiprecision::cpp_int;
using namespace std;
int main() {
    cpp_int m, x = 2;
    cin >> m;
    for (int i = 0; i < 1000000; i++) x = (x * x + 1) % m;
    cout << x << "\n";
}

string str(__int128 v) {
    if (v == 0) return "0";
    string s;
    while (v > 0) {
        s.insert(s.begin(), char('0' + int(v % 10)));
        v /= 10;
    }
    return s;
}
{
    string s;
    cin >> s;
    __int128 n = 0;
    __int128 a = 1;
    for (char c : s) n = n * 10 + (c - '0');
    for (int i = 0; i < 126; i++) a = a * 2 + 1;
    __int128 b = n * 1000000;
    cout << str(a) << "\n" << str(b / 7) << "\n" << str(b % 1000000007) << "\n" << str(n) << "\n";
    __int128 m = n / 1000000 + 9;
    __int128 x = 2;
    for (int i = 0; i < 1000000; i++) x = (x * x + 1) % m;
    cout << str(x) << "\n";
}

#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>
using boost::multiprecision::cpp_int;
using namespace std;
int main() {
    cpp_int n, f = 1;
    cin >> n;
    for (int i = 1; i <= 200; i++) f *= i;
    cpp_int m = n / 1000000 + 9;
    cpp_int x = 2;
    for (int i = 0; i < 1000000; i++) x = (x * x + 1) % m;
    cout << f << "\n" << f / n << "\n" << x << "\n";
}

#include <stdio.h>
int main(void) {
    long long m, x = 2;
    int i;
    if (scanf("%lld", &m) != 1) return 1;
    for (i = 0; i < 1000000; i++) x = (x * x + 1) % m;
    printf("%lld\n", x);
    return 0;
}

#include <stdio.h>
__extension__ typedef __int128 i128;
static void put(i128 v) {
    char buf[64];
    int n = 0;
    if (v == 0) buf[n++] = '0';
    while (v > 0) {
        buf[n++] = (char)('0' + (int)(v % 10));
        v /= 10;
    }
    while (n > 0) putchar(buf[--n]);
    putchar('\n');
}
int main(void) {
    char s[64];
    int i;
    i128 n = 0, a = 1, b, m, x = 2;
    if (scanf("%63s", s) != 1) return 1;
    for (i = 0; s[i]; i++) n = n * 10 + (s[i] - '0');
    for (i = 0; i < 126; i++) a = a * 2 + 1;
    b = n * 1000000;
    put(a);
    put(b / 7);
    put(b % 1000000007);
    put(n);
    m = n / 1000000 + 9;
    for (i = 0; i < 1000000; i++) x = (x * x + 1) % m;
    put(x);
    return 0;
}

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        long m = new Scanner(System.in).nextLong();
        long x = 2;
        for (int i = 0; i < 1000000; i++) x = (x * x + 1) % m;
        System.out.println(x);
    }
}

import java.math.BigInteger;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        BigInteger m = new Scanner(System.in).nextBigInteger();
        BigInteger x = BigInteger.TWO;
        for (int i = 0; i < 1000000; i++) x = x.multiply(x).add(BigInteger.ONE).mod(m);
        System.out.println(x);
    }
}

import java.util.Scanner;
public class Main {
    // (hi, lo) を m で割った余り。hi < m のときに使える。128 / 64 の割り算が無いので 1 ビットずつ引く
    static long rem(long hi, long lo, long m) {
        for (int i = 0; i < 64; i++) {
            hi = (hi << 1) | (lo >>> 63);
            lo <<= 1;
            if (Long.compareUnsigned(hi, m) >= 0) hi -= m;
        }
        return hi;
    }
    public static void main(String[] args) {
        long m = new Scanner(System.in).nextLong();
        long x = 2;
        for (int i = 0; i < 1000000; i++) {
            // x * x + 1 を 64 ビット 2 つ(hi, lo)で持つ
            long hi = Math.multiplyHigh(x, x);
            long lo = x * x + 1;
            if (lo == 0) hi++;
            x = rem(hi, lo, m);
        }
        System.out.println(x);
    }
}

import java.math.BigInteger;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        BigInteger n = new Scanner(System.in).nextBigInteger(), f = BigInteger.ONE;
        for (int i = 1; i <= 200; i++) f = f.multiply(BigInteger.valueOf(i));
        BigInteger m = n.divide(BigInteger.valueOf(1000000)).add(BigInteger.valueOf(9));
        BigInteger x = BigInteger.TWO;
        for (int i = 0; i < 1000000; i++) x = x.multiply(x).add(BigInteger.ONE).mod(m);
        System.out.println(f);
        System.out.println(f.divide(n));
        System.out.println(x);
    }
}

using System;
class Program {
    static void Main() {
        long m = long.Parse(Console.ReadLine().Trim()), x = 2;
        for (int i = 0; i < 1000000; i++) x = (x * x + 1) % m;
        Console.WriteLine(x);
    }
}

using System;
using System.Numerics;
class Program {
    static void Main() {
        BigInteger m = BigInteger.Parse(Console.ReadLine().Trim()), x = 2;
        for (int i = 0; i < 1000000; i++) x = (x * x + 1) % m;
        Console.WriteLine(x);
    }
}

using System;
class Program {
    static void Main() {
        Int128 n = Int128.Parse(Console.ReadLine().Trim()), a = 1;
        for (int i = 0; i < 126; i++) a = a * 2 + 1;
        Int128 b = n * 1000000;
        Console.WriteLine(a);
        Console.WriteLine(b / 7);
        Console.WriteLine(b % 1000000007);
        Console.WriteLine(n);
        Int128 m = n / 1000000 + 9, x = 2;
        for (int i = 0; i < 1000000; i++) x = (x * x + 1) % m;
        Console.WriteLine(x);
    }
}

using System;
using System.Numerics;
class Program {
    static void Main() {
        BigInteger n = BigInteger.Parse(Console.ReadLine().Trim()), f = 1;
        for (int i = 1; i <= 200; i++) f *= i;
        BigInteger m = n / 1000000 + 9, x = 2;
        for (int i = 0; i < 1000000; i++) x = (x * x + 1) % m;
        Console.WriteLine(f);
        Console.WriteLine(f / n);
        Console.WriteLine(x);
    }
}

open System
let m = Int64.Parse(Console.ReadLine().Trim())
let mutable x = 2L
for _ in 1 .. 1000000 do
    x <- (x * x + 1L) % m
printfn "%d" x

open System
let m = bigint.Parse(Console.ReadLine().Trim())
let mutable x = 2I
for _ in 1 .. 1000000 do
    x <- (x * x + 1I) % m
printfn "%s" (x.ToString())

open System
let n = Int128.Parse(Console.ReadLine().Trim())
let mutable a = Int128.One
for _ in 1 .. 126 do
    a <- a * Int128.op_Implicit 2 + Int128.One
let b = n * Int128.op_Implicit 1000000
printfn "%s" (a.ToString())
printfn "%s" ((b / Int128.op_Implicit 7).ToString())
printfn "%s" ((b % Int128.op_Implicit 1000000007).ToString())
printfn "%s" (n.ToString())
let m = n / Int128.op_Implicit 1000000 + Int128.op_Implicit 9
let mutable x = Int128.op_Implicit 2
for _ in 1 .. 1000000 do
    x <- (x * x + Int128.One) % m
printfn "%s" (x.ToString())

open System
let n = bigint.Parse(Console.ReadLine().Trim())
let f = List.fold (fun acc i -> acc * bigint (i: int)) 1I [ 1 .. 200 ]
let m = n / 1000000I + 9I
let mutable x = 2I
for _ in 1 .. 1000000 do
    x <- (x * x + 1I) % m
printfn "%s" (f.ToString())
printfn "%s" ((f / n).ToString())
printfn "%s" (x.ToString())

use strict;
my $m = <STDIN> + 0;
my $x = 2;
for (1 .. 1000000) { $x = ($x * $x + 1) % $m; }
print "$x\n";

use strict;
use Math::BigInt;
my $m = Math::BigInt->new(scalar <STDIN> =~ s/\s//gr);
my $x = Math::BigInt->new(2);
for (1 .. 1000000) {
    $x->bmul($x)->badd(1)->bmod($m);
}
print $x->bstr, "\n";

use strict;
use Math::BigInt;
my $n = Math::BigInt->new(scalar <STDIN> =~ s/\s//gr);
my $f = Math::BigInt->new(1);
$f->bmul($_) for 1 .. 200;
my $m = $n->copy->bdiv(1000000)->badd(9);
my $x = Math::BigInt->new(2);
for (1 .. 1000000) {
    $x->bmul($x)->badd(1)->bmod($m);
}
print $f->bstr, "\n", $f->copy->bdiv($n)->bstr, "\n", $x->bstr, "\n";

my int $m = get().trim.Int;
my int $x = 2;
for ^1000000 { $x = ($x * $x + 1) % $m; }
say $x;

my $m = get().trim.Int;
my $x = 2;
for ^1000000 { $x = ($x * $x + 1) % $m; }
say $x;

my $n = get().trim.Int;
my $f = [*] 1 .. 200;
my $m = $n div 1000000 + 9;
my $x = 2;
for ^1000000 { $x = ($x * $x + 1) % $m; }
say $f;
say $f div $n;
say $x;

<?php
$m = (int)trim(fgets(STDIN));
$x = 2;
for ($i = 0; $i < 1000000; $i++) $x = ($x * $x + 1) % $m;
echo $x, "\n";

<?php
$m = trim(fgets(STDIN));
$x = '2';
for ($i = 0; $i < 1000000; $i++) $x = bcmod(bcadd(bcmul($x, $x), '1'), $m);
echo $x, "\n";

<?php
$m = gmp_init(trim(fgets(STDIN)));
$x = gmp_init(2);
for ($i = 0; $i < 1000000; $i++) $x = gmp_mod(gmp_add(gmp_mul($x, $x), 1), $m);
echo gmp_strval($x), "\n";

<?php
$n = trim(fgets(STDIN));
$f = '1';
for ($i = 1; $i <= 200; $i++) $f = bcmul($f, (string)$i);
$m = bcadd(bcdiv($n, '1000000', 0), '9');
$x = '2';
for ($i = 0; $i < 1000000; $i++) $x = bcmod(bcadd(bcmul($x, $x), '1'), $m);
echo $f, "\n", bcdiv($f, $n, 0), "\n", $x, "\n";

<?php
$n = gmp_init(trim(fgets(STDIN)));
$f = gmp_init(1);
for ($i = 1; $i <= 200; $i++) $f = gmp_mul($f, $i);
$m = gmp_add(gmp_div_q($n, 1000000), 9);
$x = gmp_init(2);
for ($i = 0; $i < 1000000; $i++) $x = gmp_mod(gmp_add(gmp_mul($x, $x), 1), $m);
echo gmp_strval($f), "\n", gmp_strval(gmp_div_q($f, $n)), "\n", gmp_strval($x), "\n";

import sys
m = int(sys.stdin.readline())
x = 2
for _ in range(1000000):
    x = (x * x + 1) % m
print(x)

import sys
n = int(sys.stdin.readline())
f = 1
for i in range(1, 201):
    f *= i
m = n // 1000000 + 9
x = 2
for _ in range(1000000):
    x = (x * x + 1) % m
print(f)
print(f // n)
print(x)

m = gets.to_i
x = 2
1000000.times { x = (x * x + 1) % m }
puts x

n = gets.to_i
f = (1..200).inject(:*)
m = n / 1000000 + 9
x = 2
1000000.times { x = (x * x + 1) % m }
puts f, f / n, x

import std.stdio, std.string, std.conv;

void main() {
    long m = readln.strip.to!long, x = 2;
    foreach (i; 0 .. 1000000) x = (x * x + 1) % m;
    writeln(x);
}

import std.bigint, std.stdio, std.string;
void main() {
    BigInt m = BigInt(readln.strip), x = 2;
    foreach (i; 0 .. 1000000) x = (x * x + 1) % m;
    writeln(x);
}

import std.int128, std.stdio, std.string, std.conv;

string str(Int128 v) {
    if (v == Int128(0L)) return "0";
    string s;
    while (v > Int128(0L)) {
        s = to!string((v % Int128(10L)).data.lo) ~ s;
        v = v / Int128(10L);
    }
    return s;
}

void main() {
    Int128 n = Int128(0L), a = Int128(1L);
    foreach (c; readln.strip) n = n * Int128(10L) + Int128(cast(long)(c - '0'));
    foreach (i; 0 .. 126) a = a * Int128(2L) + Int128(1L);
    Int128 b = n * Int128(1000000L);
    writeln(str(a));
    writeln(str(b / Int128(7L)));
    writeln(str(b % Int128(1000000007L)));
    writeln(str(n));
    Int128 m = n / Int128(1000000L) + Int128(9L), x = Int128(2L);
    foreach (i; 0 .. 1000000) x = (x * x + Int128(1L)) % m;
    writeln(str(x));
}

import std.bigint, std.stdio, std.string;
void main() {
    BigInt n = BigInt(readln.strip), f = 1;
    foreach (i; 1 .. 201) f *= i;
    BigInt m = n / 1000000 + 9, x = 2;
    foreach (i; 0 .. 1000000) x = (x * x + 1) % m;
    writeln(f);
    writeln(f / n);
    writeln(x);
}

package main

import "fmt"

func main() {
	var m int64
	fmt.Scan(&m)
	x := int64(2)
	for i := 0; i < 1000000; i++ {
		x = (x*x + 1) % m
	}
	fmt.Println(x)
}

package main

import (
	"fmt"
	"math/big"
)

func main() {
	var s string
	fmt.Scan(&s)
	m, _ := new(big.Int).SetString(s, 10)
	x, one, t := big.NewInt(2), big.NewInt(1), new(big.Int)
	for i := 0; i < 1000000; i++ {
		t.Mul(x, x)
		t.Add(t, one)
		x.Mod(t, m)
	}
	fmt.Println(x)
}

package main

import (
	"fmt"
	"math/bits"
)

func main() {
	var m uint64
	fmt.Scan(&m)
	x := uint64(2)
	for i := 0; i < 1000000; i++ {
		// x * x + 1 を 64 ビット 2 つ(hi, lo)で持ち、m で割った余りを出す
		hi, lo := bits.Mul64(x, x)
		lo, carry := bits.Add64(lo, 1, 0)
		x = bits.Rem64(hi+carry, lo, m)
	}
	fmt.Println(x)
}

package main

import (
	"fmt"
	"math/big"
)

func main() {
	var s string
	fmt.Scan(&s)
	n, _ := new(big.Int).SetString(s, 10)
	f := big.NewInt(1)
	for i := int64(1); i <= 200; i++ {
		f.Mul(f, big.NewInt(i))
	}
	m := new(big.Int).Quo(n, big.NewInt(1000000))
	m.Add(m, big.NewInt(9))
	x, one, t := big.NewInt(2), big.NewInt(1), new(big.Int)
	for i := 0; i < 1000000; i++ {
		t.Mul(x, x)
		t.Add(t, one)
		x.Mod(t, m)
	}
	fmt.Println(f)
	fmt.Println(new(big.Int).Quo(f, n))
	fmt.Println(x)
}

import Data.List (foldl')

main :: IO ()
main = do
  m <- readLn :: IO Int
  let x = foldl' (\v _ -> (v * v + 1) `mod` m) 2 [1 .. 1000000 :: Int]
  print x

import Data.List (foldl')

main :: IO ()
main = do
  m <- readLn :: IO Integer
  let x = foldl' (\v _ -> (v * v + 1) `mod` m) 2 [1 .. 1000000 :: Int]
  print x

import Data.List (foldl')

main :: IO ()
main = do
  n <- readLn :: IO Integer
  let f = product [1 .. 200] :: Integer
      m = n `div` 1000000 + 9
      x = foldl' (\v _ -> (v * v + 1) `mod` m) 2 [1 .. 1000000 :: Int]
  print f
  print (f `div` n)
  print x

object Main {
  def main(args: Array[String]): Unit = {
    val m = scala.io.StdIn.readLine().trim.toLong
    var x = 2L
    var i = 0
    while (i < 1000000) {
      x = (x * x + 1) % m
      i += 1
    }
    println(x)
  }
}

object Main {
  def main(args: Array[String]): Unit = {
    val m = BigInt(scala.io.StdIn.readLine().trim)
    var x = BigInt(2)
    for (_ <- 0 until 1000000) x = (x * x + 1) % m
    println(x)
  }
}

object Main {
  // (hi, lo) を m で割った余り。hi < m のときに使える。128 / 64 の割り算が無いので 1 ビットずつ引く
  def rem(hi0: Long, lo0: Long, m: Long): Long = {
    var hi = hi0
    var lo = lo0
    var i = 0
    while (i < 64) {
      hi = (hi << 1) | (lo >>> 63)
      lo <<= 1
      if (java.lang.Long.compareUnsigned(hi, m) >= 0) hi -= m
      i += 1
    }
    hi
  }

  def main(args: Array[String]): Unit = {
    val m = scala.io.StdIn.readLine().trim.toLong
    var x = 2L
    var i = 0
    while (i < 1000000) {
      // x * x + 1 を 64 ビット 2 つ(hi, lo)で持つ
      var hi = java.lang.Math.multiplyHigh(x, x)
      val lo = x * x + 1
      if (lo == 0L) hi += 1
      x = rem(hi, lo, m)
      i += 1
    }
    println(x)
  }
}

object Main {
  def main(args: Array[String]): Unit = {
    val n = BigInt(scala.io.StdIn.readLine().trim)
    val f = (1 to 200).foldLeft(BigInt(1))(_ * _)
    val m = n / 1000000 + 9
    var x = BigInt(2)
    for (_ <- 0 until 1000000) x = (x * x + 1) % m
    println(f)
    println(f / n)
    println(x)
  }
}

import std/strutils

proc main() =
  let m = stdin.readLine().strip().parseBiggestInt().int64
  var x = 2'i64
  for _ in 1 .. 1000000: x = (x * x + 1) mod m
  echo x

main()

import std/strutils

# 判定の Nim は C++ に変換してコンパイルするので、__int128 をそのまま使う
type I128 {.importc: "__int128", nodecl.} = object

proc toI128(v: int64): I128 {.importc: "(__int128)", nodecl.}
proc lowDigit(v: I128): cint {.importc: "(int)", nodecl.}
proc `+`(a, b: I128): I128 {.importcpp: "(# + #)", nodecl.}
proc `*`(a, b: I128): I128 {.importcpp: "(# * #)", nodecl.}
proc `/`(a, b: I128): I128 {.importcpp: "(# / #)", nodecl.}
proc `%`(a, b: I128): I128 {.importcpp: "(# % #)", nodecl.}
proc `>`(a, b: I128): bool {.importcpp: "(# > #)", nodecl.}

proc str(value: I128): string =
  var v = value
  if not (v > toI128(0)): return "0"
  while v > toI128(0):
    result = $lowDigit(v % toI128(10)) & result
    v = v / toI128(10)

proc main() =
  let s = stdin.readLine().strip()
  var n = toI128(0)
  for c in s: n = n * toI128(10) + toI128(int64(ord(c) - ord('0')))
  var a = toI128(1)
  for _ in 1 .. 126: a = a * toI128(2) + toI128(1)
  let b = n * toI128(1000000)
  echo str(a)
  echo str(b / toI128(7))
  echo str(b % toI128(1000000007))
  echo str(n)
  let m = n / toI128(1000000) + toI128(9)
  var x = toI128(2)
  for _ in 1 .. 1000000: x = (x * x + toI128(1)) % m
  echo str(x)

main()

use std::io::*;
fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    let m: i64 = s.trim().parse().unwrap();
    let mut x: i64 = 2;
    for _ in 0..1000000 {
        x = (x * x + 1) % m;
    }
    println!("{}", x);
}

use num::BigInt;
use std::io::*;
fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    let m: BigInt = s.trim().parse().unwrap();
    let mut x = BigInt::from(2);
    for _ in 0..1000000 {
        x = (&x * &x + 1) % &m;
    }
    println!("{}", x);
}

use std::io::*;
fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    let n: i128 = s.trim().parse().unwrap();
    let mut a: i128 = 1;
    for _ in 0..126 {
        a = a * 2 + 1;
    }
    let b = n * 1000000;
    let m = n / 1000000 + 9;
    let mut x: i128 = 2;
    for _ in 0..1000000 {
        x = (x * x + 1) % m;
    }
    println!("{}\n{}\n{}\n{}\n{}", a, b / 7, b % 1000000007, n, x);
}

use num::BigInt;
use std::io::*;
fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    let n: BigInt = s.trim().parse().unwrap();
    let mut f = BigInt::from(1);
    for i in 1..=200 {
        f *= i;
    }
    let m = &n / 1000000 + 9;
    let mut x = BigInt::from(2);
    for _ in 0..1000000 {
        x = (&x * &x + 1) % &m;
    }
    println!("{}\n{}\n{}", f, &f / &n, x);
}

fun main() {
    val m = readLine()!!.trim().toLong()
    var x = 2L
    repeat(1000000) {
        x = (x * x + 1) % m
    }
    println(x)
}

import java.math.BigInteger

fun main() {
    val m = BigInteger(readLine()!!.trim())
    var x = 2.toBigInteger()
    repeat(1000000) { x = (x * x + BigInteger.ONE).mod(m) }
    println(x)
}

// (hi, lo) を m で割った余り。hi < m のときに使える。128 / 64 の割り算が無いので 1 ビットずつ引く
fun rem(hi0: Long, lo0: Long, m: Long): Long {
    var hi = hi0
    var lo = lo0
    repeat(64) {
        hi = (hi shl 1) or (lo ushr 63)
        lo = lo shl 1
        if (java.lang.Long.compareUnsigned(hi, m) >= 0) hi -= m
    }
    return hi
}

fun main() {
    val m = readLine()!!.trim().toLong()
    var x = 2L
    repeat(1000000) {
        // x * x + 1 を 64 ビット 2 つ(hi, lo)で持つ
        var hi = Math.multiplyHigh(x, x)
        val lo = x * x + 1
        if (lo == 0L) hi++
        x = rem(hi, lo, m)
    }
    println(x)
}

import java.math.BigInteger

fun main() {
    val n = BigInteger(readLine()!!.trim())
    var f = BigInteger.ONE
    for (i in 1..200) f *= i.toBigInteger()
    val m = n / 1000000.toBigInteger() + 9.toBigInteger()
    var x = 2.toBigInteger()
    repeat(1000000) { x = (x * x + BigInteger.ONE).mod(m) }
    println(f)
    println(f / n)
    println(x)
}

(define m (read))
(define (loop i x) (if (= i 1000000) x (loop (+ i 1) (modulo (+ (* x x) 1) m))))
(print (loop 0 2))

(define n (read))
(define (fact i acc) (if (> i 200) acc (fact (+ i 1) (* acc i))))
(define f (fact 1 1))
(define m (+ (quotient n 1000000) 9))
(define (loop i x) (if (= i 1000000) x (loop (+ i 1) (modulo (+ (* x x) 1) m))))
(print f)
(print (quotient f n))
(print (loop 0 2))

m = STDIN.gets.not_nil!.strip.to_i64
x = 2_i64
1000000.times { x = (x * x + 1) % m }
puts x

require "big"
m = STDIN.gets.not_nil!.strip.to_big_i
x = BigInt.new(2)
1000000.times { x = (x * x + 1) % m }
puts x

n = STDIN.gets.not_nil!.strip.to_i128
a = 1_i128
126.times { a = a * 2 + 1 }
b = n * 1000000
m = n // 1000000 + 9
x = 2_i128
1000000.times { x = (x * x + 1) % m }
puts a, b // 7, b % 1000000007, n, x

require "big"
n = STDIN.gets.not_nil!.strip.to_big_i
f = BigInt.new(1)
(1..200).each { |i| f *= i }
m = n // 1000000 + 9
x = BigInt.new(2)
1000000.times { x = (x * x + 1) % m }
puts f, f // n, x

func repeatSquare(_ m: Int) -> Int {
    var x = 2
    for _ in 0..<1000000 { x = (x * x + 1) % m }
    return x
}
print(repeatSquare(Int(readLine()!)!))

let n = Int128(readLine()!)!
var a: Int128 = 1
for _ in 0..<126 { a = a * 2 + 1 }
let b = n * 1000000
print(a)
print(b / 7)
print(b % 1000000007)
print(n)

func repeatSquare(_ m: Int128) -> Int128 {
    var x: Int128 = 2
    for _ in 0..<1000000 { x = (x * x + 1) % m }
    return x
}
print(repeatSquare(n / 1000000 + 9))

let () =
  let m = int_of_string (String.trim (input_line stdin)) in
  let x = ref 2 in
  for _ = 1 to 1000000 do
    x := (!x * !x + 1) mod m
  done;
  print_endline (string_of_int !x)

let () =
  let m = Z.of_string (String.trim (input_line stdin)) in
  let x = ref (Z.of_int 2) in
  for _ = 1 to 1000000 do
    x := Z.erem (Z.add (Z.mul !x !x) Z.one) m
  done;
  print_endline (Z.to_string !x)

let () =
  let n = Z.of_string (String.trim (input_line stdin)) in
  let f = ref Z.one in
  for i = 1 to 200 do f := Z.mul !f (Z.of_int i) done;
  let m = Z.add (Z.div n (Z.of_int 1000000)) (Z.of_int 9) in
  let x = ref (Z.of_int 2) in
  for _ = 1 to 1000000 do
    x := Z.erem (Z.add (Z.mul !x !x) Z.one) m
  done;
  print_endline (Z.to_string !f);
  print_endline (Z.to_string (Z.div !f n));
  print_endline (Z.to_string !x)

(let [m (Long/parseLong (clojure.string/trim (read-line)))
      x (loop [i 0 v 2]
          (if (= i 1000000) v (recur (inc i) (mod (+ (* v v) 1) m))))]
  (println x))

(let [m (bigint (clojure.string/trim (read-line)))
      x (loop [i 0 v 2N]
          (if (= i 1000000) v (recur (inc i) (mod (+' (*' v v) 1N) m))))]
  (println (str x)))

(let [n (bigint (clojure.string/trim (read-line)))
      f (reduce *' 1N (range 1 201))
      m (+' (quot n 1000000N) 9N)
      x (loop [i 0 v 2N]
          (if (= i 1000000) v (recur (inc i) (mod (+' (*' v v) 1N) m))))]
  (println (str f))
  (println (str (quot f n)))
  (println (str x)))

defmodule Main do
  def main do
    m = IO.gets("") |> String.trim() |> String.to_integer()
    x = Enum.reduce(1..1000000//1, 2, fn _, v -> rem(v * v + 1, m) end)
    IO.puts(x)
  end
end

defmodule Main do
  def main do
    n = IO.gets("") |> String.trim() |> String.to_integer()
    f = Enum.reduce(1..200, 1, fn i, acc -> acc * i end)
    m = div(n, 1000000) + 9
    x = Enum.reduce(1..1000000//1, 2, fn _, v -> rem(v * v + 1, m) end)
    IO.puts(f)
    IO.puts(div(f, n))
    IO.puts(x)
  end
end

function repeat_square(m::Int64)
    x = Int64(2)
    for _ in 1:1000000
        x = mod(x * x + 1, m)
    end
    return x
end
println(repeat_square(parse(Int64, strip(readline()))))

function repeat_square(m::BigInt)
    x = big(2)
    for _ in 1:1000000
        x = mod(x * x + 1, m)
    end
    return x
end
println(repeat_square(parse(BigInt, strip(readline()))))

n = parse(Int128, strip(readline()))
a = Int128(1)
for _ in 1:126
    global a = a * 2 + 1
end
b = n * 1000000
println(a)
println(div(b, 7))
println(rem(b, 1000000007))
println(n)

function repeat_square(m::Int128)
    x = Int128(2)
    for _ in 1:1000000
        x = mod(x * x + 1, m)
    end
    return x
end
println(repeat_square(div(n, 1000000) + 9))

function main()
    n = parse(BigInt, strip(readline()))
    f = factorial(big(200))
    m = div(n, 1000000) + 9
    x = big(2)
    for _ in 1:1000000
        x = mod(x * x + 1, m)
    end
    println(f)
    println(div(f, n))
    println(x)
end
main()

program main
  implicit none
  integer, parameter :: q = 8
  integer(q) :: m, x
  integer :: i
  read (*, *) m
  x = 2
  do i = 1, 1000000
    x = mod(x*x + 1_q, m)
  end do
  print '(I0)', x
end program

program main
  implicit none
  integer, parameter :: q = 16
  integer(q) :: n, a, b, m, x
  integer :: i
  read (*, *) n
  a = 1
  do i = 1, 126
    a = a*2 + 1
  end do
  b = n*1000000_q
  print '(I0)', a
  print '(I0)', b/7_q
  print '(I0)', mod(b, 1000000007_q)
  print '(I0)', n
  m = n/1000000_q + 9_q
  x = 2
  do i = 1, 1000000
    x = mod(x*x + 1_q, m)
  end do
  print '(I0)', x
end program

const m = BigInt(require('fs').readFileSync(0, 'utf8').trim());
let x = 2n;
for (let i = 0; i < 1000000; i++) x = (x * x + 1n) % m;
console.log(x.toString());

const n = BigInt(require('fs').readFileSync(0, 'utf8').trim());
let f = 1n;
for (let i = 1n; i <= 200n; i++) f *= i;
const m = n / 1000000n + 9n;
let x = 2n;
for (let i = 0; i < 1000000; i++) x = (x * x + 1n) % m;
console.log(f.toString());
console.log((f / n).toString());
console.log(x.toString());

declare const require: any;
const m: bigint = BigInt(require('fs').readFileSync(0, 'utf8').trim());
let x: bigint = 2n;
for (let i = 0; i < 1000000; i++) x = (x * x + 1n) % m;
console.log(x.toString());

declare const require: any;
const n: bigint = BigInt(require('fs').readFileSync(0, 'utf8').trim());
let f: bigint = 1n;
for (let i = 1n; i <= 200n; i++) f *= i;
const m: bigint = n / 1000000n + 9n;
let x: bigint = 2n;
for (let i = 0; i < 1000000; i++) x = (x * x + 1n) % m;
console.log(f.toString());
console.log((f / n).toString());
console.log(x.toString());

(let ((m (read))
      (x 2))
  (dotimes (i 1000000) (setf x (mod (+ (* x x) 1) m)))
  (format t "~d~%" x))

(let* ((n (read))
       (f (let ((r 1)) (loop for i from 1 to 200 do (setf r (* r i))) r))
       (m (+ (floor n 1000000) 9))
       (x 2))
  (dotimes (i 1000000) (setf x (mod (+ (* x x) 1) m)))
  (format t "~d~%~d~%~d~%" f (floor f n) x))

val SOME line = TextIO.inputLine TextIO.stdIn
val SOME m = Int64.fromString line
fun loop (i, x : Int64.int) = if i = 1000000 then x else loop (i + 1, (x * x + 1) mod m)
val _ = print (Int64.toString (loop (0, 2)) ^ "\n")

val SOME line = TextIO.inputLine TextIO.stdIn
val SOME m = IntInf.fromString line
fun loop (i, x : IntInf.int) = if i = 1000000 then x else loop (i + 1, (x * x + 1) mod m)
val _ = print (IntInf.toString (loop (0, 2)) ^ "\n")

val SOME line = TextIO.inputLine TextIO.stdIn
val SOME n = IntInf.fromString line
fun fact (i, acc : IntInf.int) = if i > 200 then acc else fact (i + 1, acc * IntInf.fromInt i)
val f = fact (1, 1)
val m = n div 1000000 + 9
fun loop (i, x : IntInf.int) = if i = 1000000 then x else loop (i + 1, (x * x + 1) mod m)
val _ = print (IntInf.toString f ^ "\n")
val _ = print (IntInf.toString (f div n) ^ "\n")
val _ = print (IntInf.toString (loop (0, 2)) ^ "\n")

read -r m
x=2
for ((i = 0; i < 1000000; i++)); do x=$(( (x * x + 1) % m )); done
echo "$x"

read -r m
BC_LINE_LENGTH=0 bc <<END
m = $m
x = 2
for (i = 0; i < 1000000; i++) x = (x * x + 1) % m
x
END

read -r n
# bc は既定で 70 桁ごとに行を折るので、折らないようにする
BC_LINE_LENGTH=0 bc <<END
f = 1
for (i = 1; i <= 200; i++) f *= i
m = $n / 1000000 + 9
x = 2
for (i = 0; i < 1000000; i++) x = (x * x + 1) % m
f
f / $n
x
END

module Main;

import CPLib.IO;

main : IO () = (
    let s = *read_s;
    let m : I64 = s.from_string.as_ok;
    let x = range(0, 1000000).fold(2, |_, v| (v * v + 1) % m);
    x.to_string.println;;
    pure()
);

module Main;

import CPLib.IO;
import Minilib.Math.BigInt;

big : String -> BigInt;
big = |s| from_string(s).as_ok;

main : IO () = (
    let m = big(*read_s);
    let one = big("1");
    let x = range(0, 1000000).fold(big("2"), |_, v| (v * v + one) % m);
    x.to_string.println;;
    pure()
);

module Main;

import CPLib.IO;

main : IO () = (
    let s = *read_s;
    let n : I128 = s.from_string.as_ok;
    let a = range(0, 126).fold(1_I128, |_, v| v * 2_I128 + 1_I128);
    let b = n * 1000000_I128;
    let m = n / 1000000_I128 + 9_I128;
    let x = range(0, 1000000).fold(2_I128, |_, v| (v * v + 1_I128) % m);
    a.to_string.println;;
    (b / 7_I128).to_string.println;;
    (b % 1000000007_I128).to_string.println;;
    n.to_string.println;;
    x.to_string.println;;
    pure()
);

module Main;

import CPLib.IO;
import Minilib.Math.BigInt;

big : String -> BigInt;
big = |s| from_string(s).as_ok;

main : IO () = (
    let n = big(*read_s);
    let f = range(1, 201).fold(big("1"), |i, acc| acc * big(i.to_string));
    let m = n / big("1000000") + big("9");
    let x = range(0, 1000000).fold(big("2"), |_, v| (v * v + big("1")) % m);
    f.to_string.println;;
    (f / n).to_string.println;;
    x.to_string.println;;
    pure()
);