Đường đi dài nhất

Cho đồ thị có hướng không có chu trình (DAG). Mỗi cạnh của đồ thị được gán trọng số là một số nguyên. Hãy đếm số lượng đường đi từ đỉnh $s$ đến đỉnh $t$. Trong các đường đi đó, đường đi dài nhất có giá trị bằng bao nhiêu.

Độ dài của một đường đi là tổng trọng số các cung trên đường đi đó (có thể âm). Hai đường đi được coi là khác nhau nếu dãy cung của chúng khác nhau.

Yêu cầu: Tính số lượng đường đi từ $s$ đến $t$ (theo modulo ${10}^9+7$) và tìm độ dài đường đi dài nhất từ $s$ đến $t$.

Dữ liệu vào

• Dòng đầu tiên ghi hai số nguyên dương $n,m$ ($1\le n\le 3\times {10}^5$, $1\le m\le 5\times {10}^5$) lần lượt là số đỉnh và số cạnh của đồ thị. Các đỉnh đánh số từ $1$ đến $n$.
• Dòng thứ hai ghi hai số nguyên dương $s,t$ ($1\le s,t\le n$, $s\ne t$).
• $m$ dòng tiếp theo, mỗi dòng ghi $3$ số nguyên $a,b,c$ ($1\le a,b\le n$, $a\ne b$, $|c|\le {10}^3$) thể hiện có một cung một chiều nối từ đỉnh $a$ đến đỉnh $b$ có trọng số là $c$.

Dữ liệu đảm bảo rằng đồ thị không có chu trình và không có hai cung nào cùng nối từ $a$ đến $b$.

Dữ liệu ra

• Dòng thứ nhất ghi số lượng đường đi khác nhau có thể có từ $s$ đến $t$. Vì con số này có thể rất lớn nên chỉ cần lấy phần dư của nó khi chia cho ${10}^9+7$ (phần dư này có thể bằng $0$ dù đường đi vẫn tồn tại).
• Dòng thứ hai ghi độ dài của đường đi dài nhất từ $s$ đến $t$.

Nếu không tồn tại đường đi nào từ $s$ đến $t$ thì chỉ ghi một dòng NO PATH.

Ràng buộc

• $1\le n\le 3\times {10}^5$, $1\le m\le 5\times {10}^5$.
• $1\le s,t\le n$, $s\ne t$.
• $1\le a,b\le n$, $a\ne b$, $|c|\le {10}^3$.
• Đồ thị không có chu trình, không có hai cung trùng nhau.

Subtasks

• Subtask 1 ($30\%$ số điểm): $n,m\le 10$.
• Subtask 2 ($30\%$ số điểm): $n,m\le 100$.
• Subtask 3 ($40\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ