//
// 年俸１０００万らしい・・ｗ
//
open System
 
let rec create s = function
  | 0 -> [s] 
  | n -> [ for c in "AGCT" do yield! create (s + string c) (n - 1) ]
let solve n = create "" n |> List.filter (fun s -> s.Contains "AAG")
 
solve 7 |> List.length |> printfn "%d"
 
let solve2 n = [
  for i in 1 .. pown 4 n do
    let s = String [| for n in 0..n-1 -> "AGCT".[(i>>>n*2)%4] |] 
    if s.Contains "AAG" then yield s ]
 
solve2 7 |> List.length |> printfn "%d"
 
let solve3 n = 
  let ss = ref [""]
  for _ in 1 .. n do
    ss := [ for c in "AGCT" do for s in !ss -> s + string c]
  !ss |> List.filter(fun s -> s.Contains "AAG")
 
solve3 7 |> List.length |> printfn "%d"

Ly8KLy8g5bm05L+477yR77yQ77yQ77yQ5LiH44KJ44GX44GE44O744O7772XCi8vCm9wZW4gU3lzdGVtCgpsZXQgcmVjIGNyZWF0ZSBzID0gZnVuY3Rpb24KICB8IDAgLT4gW3NdIAogIHwgbiAtPiBbIGZvciBjIGluICJBR0NUIiBkbyB5aWVsZCEgY3JlYXRlIChzICsgc3RyaW5nIGMpIChuIC0gMSkgXQpsZXQgc29sdmUgbiA9IGNyZWF0ZSAiIiBuIHw+IExpc3QuZmlsdGVyIChmdW4gcyAtPiBzLkNvbnRhaW5zICJBQUciKQoKc29sdmUgNyB8PiBMaXN0Lmxlbmd0aCB8PiBwcmludGZuICIlZCIKCmxldCBzb2x2ZTIgbiA9IFsKICBmb3IgaSBpbiAxIC4uIHBvd24gNCBuIGRvCiAgICBsZXQgcyA9IFN0cmluZyBbfCBmb3IgbiBpbiAwLi5uLTEgLT4gIkFHQ1QiLlsoaT4+Pm4qMiklNF0gfF0gCiAgICBpZiBzLkNvbnRhaW5zICJBQUciIHRoZW4geWllbGQgcyBdCgpzb2x2ZTIgNyB8PiBMaXN0Lmxlbmd0aCB8PiBwcmludGZuICIlZCIKCmxldCBzb2x2ZTMgbiA9IAogIGxldCBzcyA9IHJlZiBbIiJdCiAgZm9yIF8gaW4gMSAuLiBuIGRvCiAgICBzcyA6PSBbIGZvciBjIGluICJBR0NUIiBkbyBmb3IgcyBpbiAhc3MgLT4gcyArIHN0cmluZyBjXQogICFzcyB8PiBMaXN0LmZpbHRlcihmdW4gcyAtPiBzLkNvbnRhaW5zICJBQUciKQoKc29sdmUzIDcgfD4gTGlzdC5sZW5ndGggfD4gcHJpbnRmbiAiJWQi