Counting Alkane Isomers

Given an integer \(n\) representing the number of carbon atoms, count how many distinct acyclic alkane isomers exist (ignoring stereoisomers). In other words, you need to compute the number of unrooted, unlabeled trees with \(n\) nodes such that the degree of each node is at most \(4\).

Note: You can assume \(1 \le n \le 10\). For instance, when \(n = 1\) there is exactly one isomer, and when \(n = 4\) the answer is 2.

inputFormat

The input is a single integer \(n\) which denotes the number of carbon atoms.

outputFormat

Output a single integer: the number of distinct acyclic alkane isomers (i.e. the number of unrooted, unlabeled trees with \(n\) nodes and maximum degree \(\le 4\)).

sample

1

1