Số Catalan có nhiều ứng dụng trong các bài toán đếm tổ hợp. Sau đây là một ứng dụng: đếm số cách để chia \(n + 1\) phần tử ra thành các nhóm riêng lẻ (nói cách khác là số cách thêm các dấu đóng, mở ngoặc giữa các phần tử để được cách chia hợp lý - không bị lỗi dấu ngoặc); ví dụ, với \(n = 3\), chúng ta có 5 cách khác nhau để chia 4 phần tử: \(((ab)c)d\) ; \((a(bc))d\) ; \((ab)(cd)\) ; \(a((bc)d)\) và \(a(b(cd))\); số cách chia trên là số Catalan thứ \(n\). Người ta đã chứng minh được số Catalan có công thức tổng quát:

\(u_n = \frac{1}{n+1} C^n_{2n}\), \(n ∈ N\); một số số hạng mở đầu là \(1,1,2,5,14,42,132,...\)

Yêu cầu

Hãy xác định số Catalan thứ \(n\), kết quả có thể rất lớn nên ta cần chia lấy dư cho \(1000000007\) \((10^9+7)\).

Dữ liệu

• Dòng đầu tiên ghi số nguyên \(t\) \((0 ≤ t ≤ 10^5)\) là số lượng test.
• \(t\) dòng tiếp theo mỗi dòng ghi số nguyên \(n\) \((0 < n ≤ 10^5)\).

Kết quả

Gồm \(t\) dòng, mỗi dòng ghi tương ứng số Catalan thứ \(n\).

Ví dụ

Giới hạn

• [30%] số tests có \(t = 1, n ≤ 30.\)
• [30%] số tests có \(n ≤ 30.\)
• [40%] số tests có \(t ≤ 10^5, n ≤ 10^5\)