Counting Quartets

Problem

A quartet AB∣CD is consistent with a binary tree T if the quartet can be inferred from one of the splits of T (see “Quartets” for a description of inferring quartets from splits).

Let q(T) denote the total number of quartets that are consistent with T.

Given: A positive integer n (4≤n≤5000), followed by an unrooted binary tree T in Newick format on n taxa.

Return: The value of q(T) modulo 1,000,000.