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.

Giải các bài toán sau:

a) Tìm đường đi dài nhất từ đỉnh s đến đỉnh t

b) Đếm số lượng đường đi từ s đến đỉnh t

Input: DAG.INP

Dòng đầu tiên ghi hai số nguyên dương n, m (n<=3e5, m<=5e5) 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≤s,t≤n, s≠t)

m dòng tiếp theo, mỗi dòng ghi 3 số nguyên dương a, b, c (1≤a, b≤n, a ≠b, |c| ≤10³) 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

Output: DAG.OUT

Dòng thứ nhất 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 như vậy thì ghi "NO PATH" (không có dấu nháy kép)

Dòng thứ hai 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 chúng khi chia cho 10⁹+7