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.

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~.

Input

• 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 dương ~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.

Output

• Dòng thứ nhất ghi số lượng đường đi khác nhau có thể có từ ~s~ đến ~t~ (lấy phần dư khi chia cho ~10^9+7~). Nếu không tồn tại đường đi nào thì ghi NO PATH.
• Dòng thứ hai ghi độ dài của đường đi dài nhất từ ~s~ đến ~t~ (nếu có).

Sample Input 1

5 6
1 5
1 4 5
4 5 -4
1 2 1
2 3 2
3 5 3
1 3 -7

Sample Output 1

3
6