题目描述

给定一个 DAG（有向无环图），DAG 上每条边的长度为 $1$，你需要求出 DAG 上的最长路径长度，以及存在多少条最长路径（即最长路径的数量）。

由于最长路径的数量可能很大，所以只需要输出最长路径数量模 $10^9+7$ 的结果即可。

输入格式

第一行包含两个整数 $n$ 和 $m$，以一个空格分隔，表示节点个数和边数（$1 \le n \le 5000, 1 \le m \le 500000$）。

接下来 $m$ 行，每行包含两个整数 $u$ 和 $v$，表示 DAG 上存在一条以 $u$ 为起点 $v$ 为终点的有向边。

数据保证图中不存在环和重边。

输出格式

输出共一行，包含两个整数，以一个空格分隔。其中：

• 第一个整数表示最长路径的长度；
• 第二个整数表示最长路径的数量对 $10^9+7$ 取模的结果。

样例

6 5
1 3
2 3
3 4
3 5
3 6

2 6