# Rosalind: CUNR — Counting Unrooted Binary Trees
# https://rosalind.info/problems/cunr/
#
# Given: A positive integer n (n <= 1000).
# Return: The number of unrooted binary trees on n labeled leaves, modulo
# 1,000,000.

let n = 5
let modulus = 1000000

# An unrooted tree on n leaves is a rooted tree on n-1 leaves with the root
# edge removed, so the count drops one double-factorial step to (2n-5)!!.
let result = range(3, n + 1) |> reduce(|acc, k| (acc * (2 * k - 5)) % modulus, 1)

println("Result:   " + str(result))
println("Expected: 15   (5!! = 5 x 3 x 1)")

fn test_cunr_unrooted_binary_trees() {
    assert result == 15, "CUNR: got " + str(result)
}