CF762F Tree nesting

You are given two trees (connected undirected acyclic graphs) $ S $ and $ T $ . Count the number of subtrees (connected subgraphs) of $ S $ that are isomorphic to tree $ T $ . Since this number can get quite large, output it modulo $ 10^{9}+7 $ . Two subtrees of tree $ S $ are considered different, if there exists a vertex in $ S $ that belongs to exactly one of them. Tree $ G $ is called isomorphic to tree $ H $ if there exists a bijection $ f $ from the set of vertices of $ G $ to the set of vertices of $ H $ that has the following property: if there is an edge between vertices $ A $ and $ B $ in tree $ G $ , then there must be an edge between vertices $ f(A) $ and $ f(B) $ in tree $ H $ . And vice versa — if there is an edge between vertices $ A $ and $ B $ in tree $ H $ , there must be an edge between $ f^{-1}(A) $ and $ f^{-1}(B) $ in tree $ G $ .

The first line contains a single integer $ |S| $ ( $ 1

On the first line output a single integer — the answer to the given task modulo $ 10^{9}+7 $ .