Thủ đô Sierpinski của thành phố Fractal mới thực hiện công cuộc quy hoạch đô thị một bãi đất trống rộng lớn ở rìa trung tâm thành phố. Tade - chủ đầu tư dự án nghìn tỷ này - quyết định phân vùng bãi đất này thành hai khu: khu dân cư và khu thương mại. Vùng dân cư sẽ được tô màu xanh biển và vùng thương mại sẽ được tô màu trắng như hình minh họa ở dưới:

Để tránh việc cấp dư hoặc thiếu đất cho những chủ doanh nghiệp nơi đây, Tade cần biết chính xác số tam giác trong vùng thương mại. Cụ thể hơn, cho trước một số nguyên dương \(n\), các bạn hãy tính số tam giác màu trắng của hình trên dựa trên quy luật đã được cung cấp nhé!

Input

• Một dòng duy nhất chứa một số nguyên \(n\) \((0 \le n \le 10^5)\).

Output

• In ra số lượng tam giác màu trắng sau khi chia lấy dư cho \(10^9 + 7\).

Example

0

0

3

13