问题文

高桥君所在的大学每年迎来 $N$ 名新生。新生们的学籍号从 $1$ 到 $N$ 连续编号，高桥君的学籍号是 $1$。
现在，从4月开始上大学的高桥君希望和其他 $N-1$ 名新生都成为朋友。然而，为了实现这个目标需要付出很高的代价。
对于高桥君来说，“和x君是朋友”指的是通过一系列交友关系可以到达x君的状态。

目前，新生们彼此互不认识，没有任何学生是彼此的朋友。显然，高桥君也没有任何朋友。然而，高桥君知道 $M$ 种形式为“花费 $C$ 日元将学籍号为 $A$ 的学生和学籍号为 $B$ 的学生变成朋友”的方式（其中可能包括高桥君本人）。此外，由于每个学生的需求不同，具有相同费用的方式数量并不偏向某一方面。
最初，除了高桥君之外，新生中没有朋友，高桥君计划利用上述方式与所有新生成为朋友。此外，高桥君无法通过其他方式交朋友。然而，高桥君的资金有限，他希望用尽量少的费用与所有新生交朋友。由于高桥君很忙，所以他决定将这个任务交给你作为程序员来完成。

高桥君向您介绍了工作。

首先，您会收到在大学就读的新生数量 $N$（包括高桥君）以及方式的数量 $M$，以及 $M$ 种方式的信息。新生们的学籍号从 $1$ 到 $N$ 连续编号，高桥君的学籍号是 $1$。
您的任务是输出高桥君与所有新生成为朋友所需的总费用，以及达到最低费用的方式的数量，然后将结果对 $1,000,000,007$ 取模。

输入

输入以以下格式从标准输入中提供。

$N　M