กำหนดจำนวน $n$ งานของคุณคือนับลำดับสามเหลี่ยมทั้งหมด และแสดงผลเศษเหลือจากการหารจำนวนที่นับได้ด้วย $10^9 + 7$ ลำดับหนึ่งจะเรียกว่าลำดับสามเหลี่ยมก็ต่อเมื่อเป็นไปตามเงื่อนไขต่อไปนี้:

• ความยาวของลำดับไม่เกิน $n$
• แต่ละสมาชิกเป็นจำนวนเต็มในช่วง $[1, n]$
• มีสมาชิกสามตัวใด ๆ ของลำดับนี้ที่สามารถเป็นความยาวด้านของรูปสามเหลี่ยมไม่ลดรูป*ได้

ตัวอย่างลำดับสามเหลี่ยมสำหรับ $n = 100$ ได้แก่ $(1, 1, 1)$ และ $(16, 1, 11, 25, 100)$ ในลำดับแรก ด้านของรูปสามเหลี่ยมไม่ลดรูปคือ $(1, 1, 1)$ และในลำดับที่สองคือ $(16, 11, 25)$

ลำดับ $(16, 1, 11, 84, 100)$ ไม่ใช่ลำดับสามเหลี่ยม เพราะไม่มีสมาชิกสามตัวใดประกอบกันเป็นด้านของรูปสามเหลี่ยมไม่ลดรูปได้ ลำดับ $(5, 5)$ ก็ไม่ใช่ลำดับสามเหลี่ยมเช่นกัน

* รูปสามเหลี่ยมจะเรียกว่าไม่ลดรูปหากมีพื้นที่เป็นบวก หรือกล่าวอีกนัยหนึ่งคือจุดยอดทั้งสามไม่อยู่บนเส้นตรงเดียวกัน

ข้อมูลนำเข้า

บรรทัดเดียวประกอบด้วยจำนวนเต็ม $n$ ($3 \le n \le 200\,000$)

ข้อมูลส่งออก

แสดงผลจำนวนเต็มเพียงจำนวนเดียว คือเศษเหลือจากการหารจำนวนลำดับสามเหลี่ยมด้วย $10^9 + 7$ (กล่าวคือ $1000000007$)

ตัวอย่าง

ข้อมูลนำเข้า 1

3

ข้อมูลส่งออก 1

15

ข้อมูลนำเข้า 2

4

ข้อมูลส่งออก 2

254

หมายเหตุ

สำหรับ $n = 3$ มีลำดับสามเหลี่ยม $15$ ลำดับ: $(1,1,1), (1,2,2), (1,3,3), (2,1,2), (2,2,1), (2,2,2), (2,2,3), (2,3,2), (2,3,3), (3,1,3), (3,2,2), (3,2,3), (3,3,1), (3,3,2), (3,3,3)$

สำหรับ $n = 4$ มีลำดับสามเหลี่ยม $254$ ลำดับ: $(1,1,1), (1,1,1,1), (1,1,1,2), (1,1,1,3), (1,1,1,4), (1,1,2,1), \dots, (4,4,2,4), (4,4,3), (4,4,3,1), (4,4,3,2), (4,4,3,3), (4,4,3,4), (4,4,4), (4,4,4,1), (4,4,4,2), (4,4,4,3), (4,4,4,4)$