[Bài 2 trong chuỗi bài Mỗi tuần một bài toán 2025]

Các coder có thể xem thông tin thêm tại đây: Thông tin về contest

Trong đề Olympic bảng chuyên Tin 2024 vừa qua đã có một bài toán khá thú vị là đếm số tam giác đều trên lưới. Nếu biết công thức là ~C_{n+4}^4~, thí sinh có thể AC nhanh chóng được các sub-task đầu. Tiếp tục ý tưởng đó, mời các bạn thử sức với bài toán sau đây, vẫn trên mô hình lưới tam giác đều:

Cho một tam giác đều mà trên mỗi cạnh của nó có chứa ~n~ điểm chia cạnh đó thành các phần bằng nhau. Nối các điểm chia lại với nhau bởi các đoạn thẳng song song với cạnh tam giác lớn để có một lưới tam giác đều. Các vị trí giao điểm được đánh dấu, được gọi là điểm nút (tính cả đỉnh của tam giác lớn), còn các tam giác chia ra được gọi là tam giác con. Câu hỏi đặt ra bao gồm:

(1) Đếm số hình bình hành có 4 đỉnh là 4 nút của lưới và các cạnh song song với cạnh của tam giác lớn.

(2) Đếm số đường đi từ tam giác đỉnh đến tam giác chính giữa ở dưới cùng, thông qua dãy tam giác kề cạnh, không cho đi lặp lại và không cho đi ngược lên hàng phía trên.

Input. Số nguyên dương ~n~ với ~1 \le n \le 10^6~.

Output. Hai kết quả cần tìm, vì đáp số có thể rất lớn nên lấy số dư khi chia cho ~10^9+7.~

Sample input

3

Sample output

45 6