import System.Environment
import Prelude hiding (sum,seq)

class Semiring s where
  zero, one :: s
  plus, times :: s -> s -> s

instance Semiring Bool where
  zero = False
  one = True
  plus = (||)
  times = (&&)

data Reg c s = Reg {
  empty :: !s,
  final :: !s,
  reg   :: Re c s
}

data Re c s
  = Eps
  | Sym (c -> s)
  | Alt (Reg c s) (Reg c s)
  | Seq (Reg c s) (Reg c s)
  | Rep (Reg c s)

eps :: Semiring s => Reg c s
eps = Reg {
    empty = one,
    final = zero,
    reg = Eps
  }

sym :: Semiring s => (c -> s) -> Reg c s
sym f = Reg {
    empty = zero,
    final = zero,
    reg = Sym f
  }

alt :: Semiring s => Reg c s -> Reg c s -> Reg c s
alt p q = Reg {
    empty = empty p `plus` empty q,
    final = final p `plus` final q,
    reg = Alt p q
  }

seq :: Semiring s => Reg c s -> Reg c s -> Reg c s
seq p q = Reg {
    empty = empty p `times` empty q,
    final = (final p `times` empty q) `plus` final q,
    reg = Seq p q
  }

rep :: Semiring s => Reg c s -> Reg c s
rep r = Reg {
    empty = one,
    final = final r,
    reg = Rep r
  }

shift :: Semiring s => s -> Re c s -> c -> Reg c s
shift _ Eps       _ = eps
shift m (Sym f)   c = (sym f) { final = m `times` f c }
shift m (Alt p q) c = alt (shift m (reg p) c) (shift m (reg q) c)
shift m (Seq p q) c = seq (shift m (reg p) c) (shift ((m `times` empty p) `plus` final p) (reg q) c)
shift m (Rep r)   c = rep (shift (m `plus` final r) (reg r) c)

match :: Semiring s => Reg c s -> [c] -> s
match r [] = empty r
match r (c:cs) = final (foldl (shift zero . reg) (shift one (reg r) c) cs)

test n = match re (replicate n 'a') where
  a = sym ('a'==)
  seqn = foldr1 seq . replicate n
  re = seqn (a `alt` eps) `seq` seqn a

main = do
    [arg] <- getArgs
    print $ test $ read arg