Kim tự tháp

Bình rất thích hình kim tự tháp nên đã mua một trò chơi ghép hình gồm nhiều hình khối lập phương.

Kim tự tháp được ghép theo cách sau: tầng trên cùng có \(1\) khối, tầng thứ \(2\) có \(1 + 2 = 3\) khối, tầng thứ \(3\) có \(1 + 2 + 3 = 6\) khối, cứ như vậy cho các tầng ở dưới.

Bình muốn xây dựng một kim tự tháp có chiều cao \(h\) thì Bình cần phải có bao nhiêu khối hộp lập phương?

Yêu cầu. Lập trình tính số khối hộp lập phương với chiều cao \(h\) cho trước.

Input

Nhập từ bàn phím số nguyên dương \(h\) là chiều cao của kim tự tháp.

Output

In ra màn hình là số khối hộp lập phương cần dùng chia dư cho \(10^9\).

Example

Input:

3

Output:

10

Input:

4

Output:

20

Notes

Với \(h = 3\):

• Tầng \(1\) có \(1\) khối;

• Tầng \(2\) có \(1 + 2 = 3\) khối;

• Tầng \(3\) có \(1 + 2 + 3 = 6\) khối.

Tổng số khối là \(1 + 3 + 6 = 10\).

Với \(h = 4\):

• Tầng \(1\) có \(1\) khối;

• Tầng \(2\) có \(3\) khối;

• Tầng \(3\) có \(6\) khối;

• Tầng \(4\) có \(10\) khối.

Tổng số khối là \(1 + 3 + 6 + 10 = 20\).

Scoring

• (60%) \(1 \le h \le 200\);

• (30%) \(1 \le h \le 10^6\);

• (10%) \(1 \le h \le 10^9\).