MainKing has a rooted tree with

nodes, and

paths on it. And the root of this tree is

.
The endpoints of the i-th path are

. All of these paths satisfy a special condition:

is on the path from

to the root.
Now MianKing wants to delete all of these paths. He will do the following operation until all of the paths are deleted: choose an integer

from

randomly and delete all of the paths where

is on.
MianKing wants you to calculate the expected number of operations he need to do.
It's guaranteed that the answer will converge to some rational number.
If the answer is irreducible fraction

, you need to output an integer

in

which satisfies

. It's guaranteed that
