code jam 1c B

gistfile1.py

import sys
from collections import defaultdict

def shorten(p):
    new_p = [p[0]]
    last = p[0]
    for c in p:
        if c == last:
            continue
        last = c
        new_p.append(c)

    return ''.join(new_p)

def C(n):
    if n == 0: return 1
    if n == 1: return 1
    return n * C(n-1)

def count(st, m, rm, l, id=None):
    if len(rm[st]) > 1 or (len(rm[st]) == 1 and len(rm[st].values()[0]) > 1):
        # if there is more than one way to the node
        return 0
    if len(m[st]) > 1 or (len(m[st]) == 1 and len(m[st].values()[0]) > 1):
        # if there is more than one way to leave the node
        return 0
    elif len(m[st]) == 0:
        # if it is the final node
        return C(len(l[st]))

    # should be only one
    next_st, next_id = m[st].items()[0]
    next_id = list(next_id)[0]

    if id == next_id and st in l:
        return 0

    return C(len(l[st])) * count(next_st, m, rm, l, next_id)

def solve(ps):
    ps = dict((id, shorten(k)) for id, k in enumerate(ps))

    m = defaultdict(lambda: defaultdict(lambda : set()))
    rm = defaultdict(lambda: defaultdict(lambda : set()))
    l = defaultdict(lambda: set())
    for id in ps:
        q = ps[id]

        if len(q) == 1:
            l[q[0]].add(id)
        else:
            for i in xrange(len(q)-1):
                m[q[i]][q[i+1]].add(id)
                rm[q[i+1]][q[i]].add(id)

    # print [ps[k] for k in ps]
    # find starting point
    sts = set([k for k in m if not rm[k]] + [k for k in l if not rm[k]])
    # print sts

    if not sts:
        return 0

    vs = []
    for st in sts:
        v = count(st, m, rm,  l)
        if v == 0:
            return 0

        vs.append(v)

    # print vs
    return reduce(lambda i,j: i*j, vs, C(len(vs)))

def main(input):
    T = int(input.readline())
    global cache
    for t in range(T):
        cache = {}
        print "Case #%s:"% (t+1),

        N = int(input.readline())

        ps = input.readline().split()

        print solve(ps) %  1000000007


main(sys.stdin)