---

Problem 270

---

Xem đề gốc (tiếng Anh)

Cắt hình vuông

Mảnh giấy hình vuông $N \times N$ được cắt bằng các đường thẳng từ điểm nguyên trên một cạnh đến điểm nguyên trên cạnh khác (không giao nhau).

Tính số cách cắt hợp lệ cho $N = 10^{14}$, modulo $10^8$.

---