2967: 不三不四树

Aponoia 历经千辛万苦，终于住进了自己的别墅，开始享受新的生活。 一日，Aponoia 正在潜心研究树结构。突然，Aponoia 的脑海中蹦出不三不 四这个词。Aponoia 看了看刚刚画在草稿纸上的两棵满二叉树——高度分别为 3 和 4，即分别由 7 个和 15 个节点构成的满二叉树，Aponoia 开始 YY 下面这个难题： 首先引入 lca（x，y）这个记号，表示 x 和 y 两个节点在树上的最近公共祖 先。然后 Aponoia 定义了“不三不四树”。假设在一棵有根树上存在五个互不相同 的节点，分别记为 a ，b ，c ，d ，z ，若这 5 个点同时满足以下要求： a，b，c，d，lca（a，b），lca（c，d），lca（lca（a，b），lca（c，d））这 7 个节点互不相同，并且 z 是 lca（lca（a，b），lca（c，d））的祖先；那么五元 组（a ，b ，c ，d ，z ）表示了一棵合法的“ 不三不四树” 。同时，交换 a，b，c，d，z 的顺序只算作一种。 现在给定一棵以 1 号节点为根的树，请你求出满足上述要求的“不三不四 树”的总数。由于答案可能很大，请输出答案mod 1234567891 后的结果。

第一行一个正整数n，表示树的节点数。第二至n 行每行两个正整数x，y（x < y），表示节点x 是节点y 的父节点。

一行一个整数，表示“不三不四树”的种数 mod 1234567891 后的结果。

10
1 2
2 3
34
35
4 6
4 7
4 8
5 9
5 10

6