open Batteries
open Printf

let ($) g f x = g (f x)

let swap = Tuple2.swap

let s2i = int_of_string
let i2s = string_of_int
let s2f = float_of_string
let f2s = string_of_float
let f2i = int_of_float
let i2f = float_of_int 

let c2a = int_of_char
let a2c = char_of_int

let c2i c = c2a c - 48
let i2c i = a2c (i + 48)

let c2s = String.of_char
let s2cl = String.to_list
let cl2s = String.of_list

let puts s = print_endline s
let putw ?yn:(yn=("Yes", "No")) b = puts (if b then fst yn else snd yn)
let puti i = puts @@ i2s i



module StaleList = struct
  include List

  let nmem x l = not @@ mem x l

  let len = length
  let size = length
  let nempty l = not @@ is_empty l

  let hdop l = if nempty l then Some (hd l) else None

  (* let taker = drop *)
  let takewh = take_while

  (* let dropr = take *)
  let dropwh = drop_while

  let split_by = span

  let chunk = ntake

  let foldl = fold_left
  let foldli = fold_lefti
  let foldr f z l = fold_right f l z
  let foldri f z l = fold_righti f l z

  let partition_to_map f l =
    foldr (fun x m -> Map.modify_opt (f x) (function
      | None -> Some [x] 
      | Some [] -> Some [x] 
      | Some vl -> Some (x::vl)) m) Map.empty l;;

  let scanl f z ls =
    let rec loop acl acc = function
      | [] -> rev acl
      | h::t ->
        let r = f acc h in
        loop (r::acl) r t
    in loop [] z ls

  let scanr f z ls =
    let rec loop acl acc = function
      | [] -> acl 
      | h::t ->
        let r = f h acc in
        loop (r::acl) r t
    in loop [] z (rev ls)

  (* let scanli = scan_lefti *)
  (* let scanri = scan_righti *)
  
  let flatmap = concat_map

  let zipf = map2
  let zipfi = map2i

end

module L = StaleList

module StaleArray = struct
  include Array 

  let nmem x l = not @@ mem x l

  let len = length
  let size = length
  let is_empty r = len r = 0
  let nempty r = len r > 0

  let take n r = left r n
  let taker n r = right r n

  let takeb x r =
    let l = len r in
    let rec loop i =
      if i >= l then r
      else if r.(i) = x then take i r
      else loop (i + 1)
    in loop 0
     
  (* let takewh = take_while *)

  let drop n r = tail r n
  let dropr n r = take ((len r) - n) r
  (* let dropwh = drop_while *)

  let index_of x r =
    let l = len r in
    let rec loop i =
      if i >= l then None
      else if r.(i) = x then Some i
      else loop (i + 1)
    in loop 0

  (* let split_by = span *)

  (* let chunk = ntake *)

  let foldl = fold_left
  let foldli = fold_lefti
  let foldr f z l = fold_right f l z
  let foldri f z l = fold_righti f l z

  (* let partition_to_map f l = *)
  (*   foldr (fun x m -> Map.modify_opt (f x) (function *)
  (*     | None -> Some [x]  *)
  (*     | Some [] -> Some [x]  *)
  (*     | Some vl -> Some (x::vl)) m) Map.empty l;; *)

  (* let scanl = scan_left *)
  (* let scanli = scan_lefti *)
  (* let scanr = scan_right *)
  (* let scanri = scan_righti *)
  
  let concat2 = append
  
  let flatmap (f : 'a -> 'b array) a =
    map f a |> enum |> L.of_enum |> concat

  let zipf = map2
  (* let zipfi = map2i *)

end

module A = StaleArray

module StaleString = struct
  include String

  let len = length

  let replace_chars = map
  let map = replace

  let maptol f s = L.map f (s2cl s)
  let maptoli f s = L.map f (s2cl s)

  let zipf f a b = L.zipf f (s2cl a) (s2cl b)
  let zipfi f a b = L.zipfi f (s2cl a) (s2cl b)

  let mkstr f sep ls =
    L.foldl (fun acc x -> acc ^ sep ^ (f x)) (f @@ L.hd ls) (List.tl ls)

end

module S = StaleString

let spsp s = S.split_on_char ' ' s


module StaleSortedSet = struct
  include Set

  module Make (Ord : Set.OrderedType) = struct
    include Set.Make(Ord)

    let nempty st = not @@ is_empty st
    let sing = singleton
    let nmem x st = not @@ mem x st

    let foldl f s z = fold (fun x a -> f a x) z s

    let size = cardinal
  end

  let nempty st = not @@ is_empty st
  let sing = singleton
  let nmem x st = not @@ mem x st

  let foldl f s z = fold (fun x a -> f a x) z s

  let size = cardinal
end

module Ss = StaleSortedSet

module StaleSortedMap  = struct
  include Map

  module Make (Ord : Map.OrderedType) = struct
    include Map.Make(Ord)

    let nempty st = not @@ is_empty st
    let sing = singleton
    let nmem x st = not @@ mem x st

    let get = find
    let get_or x d m = find_default d x m

    let size = cardinal
  end

  let nempty st = not @@ is_empty st
  let sing = singleton
  let nmem x st = not @@ mem x st

  let get = find
  let get_or x d m = find_default d x m

  let size = cardinal
end

module Ms = StaleSortedMap


module StaleRange = struct

  type t = Range of int * int

  let make lb ub = Range (lb, ub)

  let to_list r =
    let Range (lb, ub) = r in
    L.make (ub - lb) ((+) lb) 

  let to_array r =
    let Range (lb, ub) = r in
      A.make (ub - lb) ((+) lb)

  let iter r f = 
    let Range (lb, ub) = r in
    for i = lb to ub do f i done

  let iter2 r1 r2 f =
    let Range (lb1, ub1) = r1 and Range (lb2, ub2) = r2 in
      for i = lb1 to ub2 do
        for j = lb2 to ub2 do
          f i j
        done
      done
end

module R = StaleRange

let (--) lb ub = R.make lb ub
let (--^) lb ub = R.make lb (ub - 1)

module StaleGenericAlgorithms = struct

  let set_power ls =
    let rec loop ls pls =
      match ls with
      | [] -> pls
      | hd::tl -> loop tl (L.flatmap (fun p -> [p; hd::p]) pls)
    in loop ls [[]]

  let rec bsearch_max_int f lb ub =
    if lb >= ub then (if f lb then lb else (lb - 1))
    else (
      let m = (lb + ub) / 2 in
      if f m then bsearch_max_int f (m + 1) ub
      else bsearch_max_int f lb m
    )

  let partial_sum n ls =
    let rec loop s k = function
      | [] -> s
      | h::t ->
        if k >= n then s
        else loop (s + h) (k + 1) t
    in
    loop 0 0 ls

end

module Gal = StaleGenericAlgorithms

let rds () = read_line ()

let rdi () = s2i @@ rds ()

let rdhs () = spsp @@ rds ()
let rdhi () = rdhs () |> L.map s2i

let rdhf () = rdhs () |> L.map s2f

let rdf2 () = match rdhf () with
| a::b::_ -> (a, b)
| _ -> (0., 0.)

let rdf3 () = match rdhf () with
| a::b::c::_ -> (a, b, c)
| _ -> (0., 0., 0.)

let rdf4 () = match rdhf () with
| a::b::c::d::_ -> (a, b, c, d)
| _ -> (0., 0., 0., 0.)

let rds2 () = match rdhs () with
  | a::b::_ -> (a, b)
  | _ -> ("", "")

let rdi2 () = match rdhi () with
  | a::b::_ -> (a, b)
  | _ -> (0, 0)

let rdi3 () = match rdhi () with
| a::b::c::_ -> (a, b, c)
| _ -> (0, 0, 0)

let rdi4 () = match rdhi () with
| a::b::c::d::_ -> (a, b, c, d)
| _ -> (0, 0, 0, 0)

let rdi5 () = match rdhi () with
| a::b::c::d::e::_ -> (a, b, c, d, e)
| _ -> (0, 0, 0, 0, 0)

let rdv n rf =
  let rec loop n =
    if n <= 0 then []
    else (
      let s = rf () in
      s::(loop (n - 1))
    )
  in loop n

let rdvi n = rdv n rdi
let rdvi2 n = rdv n rdi2
let rdvi3 n = rdv n rdi3
let rdvi4 n = rdv n rdi4


let print_list aa = 
  printf "[ "; aa |> L.iter (fun a -> printf "%d " a); puts "]"

let print_array aa = 
  printf "[ "; aa |> A.iter (fun a -> printf "%d " a); puts "]"

let print_carray aa = 
  printf "[ "; aa |> A.iter (fun a -> printf "%c " a); puts "]"

let print_matrix mat =
  puts "----";
  mat |> A.iter (fun r -> print_carray r);
  puts "----"


let rec pow_mod x e m =
  let rec loop a e' =
    if e' = 0 then a mod m
    else loop ((a * x) mod m) (e'-1)
  in
  loop 1 e

let ext_euclid a b =
  let rec next (r0, s0, t0) (r1, s1, t1) =
    match r1 with
    | 0 -> (r0, s0, t0)
    | r2 ->
      let q = r0 / r1 in
      next (r1, s1, t1) (r0 - q * r1, s0 - q * s1, t0 - q * t1)
  in
  if a < b then
    let (g, y, x) = next (b, 1, 0) (a, 0, 1) in (g, x, y)
  else
    next (a, 1, 0) (b, 0, 1)

let modinv x m =
  let (g, y, z) = ext_euclid x m in
  match g with
  | 1 -> y mod m
  | _ -> invalid_arg "Not relatively prime"
    
let rec fact_mod x m =
  let rec loop a x' =
    if x' <= 0 then a
    else loop ((x' * a) mod m) (x' - 1)
  in loop 1 x

let binom_mod n k m =
  let a = fact_mod n m in
  let b = fact_mod k m in
  let c = fact_mod (n - k) m in
  (a * modinv (b * c) m) mod m


module StaleFFT = struct

  let complex_cooley_tukey ps ar =

    let rec part e d ba =
     ()
    in

  ()
end

let _ =
  let prim = 1000000007 in

  let n = rdi () in
  
  let ss = L.make n "ACL" in
    puts @@ S.concat "" ss;
  ()


Measured memory_bytes: 5400