d.py

memo = {}

def solve_recursive(s, a, b, ch):
    def with_memo(x):
        if (s,a,b,ch) not in memo:
            memo[(s,a,b,ch)] = x % 1000000007
        return memo[(s,a,b,ch)]

    if (s,a,b,ch) in memo:
        return memo[(s,a,b,ch)]

    if s == '':
        if a != 0 or b != 0 or ch != 'a' or ch == '':
            return with_memo(0)
        else:
            return with_memo(1)

    if s.count('a') < a or s.count('b') < b:
        return 0

    x = solve_recursive(s[:-1], a, b, ch)

    if ch == 'a' and a == 0 and b == 0:
        return with_memo(1 + solve_recursive(s, a, b, ''))

    if ch == '' and s[-1] == 'd' or ch == 'd' and s[-1] == 'd':
        return with_memo(x + solve_recursive(s[:-1], a, b+1, 'd'))
    elif ch == 'd' and s[-1] == 'c' or ch == 'c' and s[-1] == 'c':
        return with_memo(x + solve_recursive(s[:-1], a+1, b, 'c'))
    elif ch == 'c' and s[-1] == 'b':
        return with_memo(x + solve_recursive(s[:-1], a, b-1, 'b'))
    elif ch == 'b' and s[-1] == 'b':
        y = solve_recursive(s[:-1], a, b-1, 'b') if b > 0 else 0
        return with_memo(x + y)
    elif ch == 'b' and s[-1] == 'a' or ch == 'a' and s[-1] == 'a':
        y = solve_recursive(s[:-1], a-1, b, 'a') if a > 0 else 0
        return with_memo(x + y)
    return with_memo(x)


def solve(s):
    return solve_recursive(s, 0, 0, '') % 1000000007

for i in range(1, int(input())+1):
    memo = {}
    print ("Case #{}: {}".format(i, solve(input())))

d.scala

import java.io.PrintStream
import scala.io.Source

object DNA {
  def solve(dna: String): Long = {
    val memo = scala.collection.mutable.HashMap[(Int, Int, Int, Char), Long]()
    def _solve(i:Int, a:Int, b:Int, ch:Char):Long = {
      lazy val s = dna.take(i)
      lazy val x = _solve(i-1,a,b,ch)
      if (i == 0)
        (if (a == 0 && b == 0 && ch == 'a') 1 else 0)
      else memo.getOrElseUpdate((i,a,b,ch), {(ch, dna(i-1)) match {
        case (_,_) if (s.count(_=='a') < a || s.count(_=='b') < b) => 0
        case (' ','d') | ('d','d') => x + _solve(i-1,a,b+1,'d')
        case ('d','c') | ('c','c') => x + _solve(i-1,a+1,b,'c')
        case ('c','b') | ('b','b') if (b > 0) => x + _solve(i-1,a,b-1,'b')
        case ('b','a') | ('a','a') if (a > 0) => x + _solve(i-1,a-1,b,'a')
        case ('a',_) if a == 0 && b == 0 => 1 + _solve(i,a,b,' ')
        case (_, _) => x
      }} % 1000000007)
    }
    println(s"starting $dna")
    _solve(dna.length, 0, 0, ' ')
  }

  def main(args: Array[String]): Unit = {
    // val INPUT = "2.in"
    val INPUT = "D-large-practice.in"
    val OUTPUT = INPUT.takeWhile(_ != '.') + ".out"
    val isConsole = false

    val itr = Source.fromFile(INPUT).getLines()
    val stream = if (isConsole) Console.out else new PrintStream(OUTPUT)
    try {
      val sets = itr.next().toInt
      (1 to sets).foreach { set =>
        stream.println(f"Case #$set: ${solve(itr.next())}")
      }
    } finally {
      stream.flush()
      if (!isConsole) stream.close()
    }
  }
}