Một bộ bài \(52\) lá (4 chất, mỗi chất \(13\) lá). Rút ngẫu nhiên \(K\) lá. Tính xác suất có ít nhất một đôi (hai lá cùng số). Kết quả modulo \(10^9+7\).

Định dạng đầu vào

• Một dòng chứa số nguyên \(K\) (\(1 \le K \le 52\)).

Định dạng đầu ra

• Một số nguyên là xác suất modulo \(10^9+7\).

Ví dụ

Input:

2

Output:

11764706

Giải thích: Xác suất 2 lá tạo thành đôi = \(C(13,1) \times C(4,2) / C(52,2) = 78 / 1326 \approx 0.0588\). Modulo 1e9+7 = 11764706.

Ràng buộc

• 100% số điểm: \(K \le 52\).