Bài tập

\begincenter

\endcenter

Example

123123

123

123321

-1

Sở thú có một cầu thang gồm \(n\) bậc dẫn từ bờ suối lên đỉnh đồi. Một chú thỏ có thể thực
hiện một bước nhảy lên được \(1\) bậc hoặc \(2\) bậc hoặc \(3\) bậc của cầu thang. Lần nào đi lên cầu
thang này, chú thỏ đều thực hiện trình tự các bước nhảy sao cho bước nhảy lần sau không ít
bậc hơn bước nhảy trước đó.

Yêu cầu: Đếm số lượng các cách đi lên cầu thang khác nhau mà chú thỏ có thể thực hiện
được. Biết rằng hai cách đi được xem là khác nhau nếu có ít nhất một bước nhảy khác nhau.

Input

Đọc từ tệp văn bản CAU4.INP một số nguyên dương \(n\).

Output

Ghi ra tệp văn bản CAU4.OUT một số duy nhất là số cách đi lên cầu thang khác
nhau mà chú thỏ có thể thực hiện được. Nếu số cách đi có nhiều hơn sáu chữ số thì chỉ ghi sáu chữ số cuối cùng của nó (mod 1000000).

Example

6

7

Scoring

Có \(20\%\) số điểm có \(1 ≤ n ≤ 10^2\)

Có \(30\%\) số điểm có \(10^2 < n ≤ 5 × 10^3\)

Có \(50\%\) số điểm có \(5 × 10^3 < n < 10^6\)

Viết chương trình nhập vào từ bàn phím số nguyên dương \(n\) (\(1 \leq n \leq 19)\). Đưa ra kết quả của \(n!\). \((n! = 1 \times 2 \times 3 \times 4 \cdots \times n)\).

Input

Gồm một dòng là một số nguyên duy nhất là \(n\)

Output

In ra kết quả bài toán.

Example

3

6

4

24

5

120

Một số nguyên dương \(N\) được gọi là số hoàn hảo khi \(N\) bằng tổng các ước nguyên dương khác nó. Ví dụ: \(6\) có các ước nguyên dương khác nó là: \(1, 2, 3\) và \(1 + 2 + 3 = 6\) hay \(6\) là một số hoàn hảo, \(5\) không phải là số hoàn hảo.

Yêu cầu: Cho số nguyên dương \(N\) , hãy kiểm tra \(N\) có phải là một số hoàn hảo hay không?

Input

Nhập từ bàn phím số nguyên dương \(N\) \((1 ≤ N ≤ 1000000)\).

Output

Ghi ra màn hình một trong hai thông báo: "So hoan hao." hoặc "Khong phai la so hoan
hao.".

Example

6

So hoan hao.

5

Khong phai la so hoan hao.