Bài tập

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

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\)

\begincenter

\endcenter

Example

123123

123

123321

-1

Trong nhà mèo Tôm ban đầu có \(N\) hạt thóc. Vụ mùa đến, mèo Tôm dành một ngày đi thu hoạch
thóc mang về nhà rồi ngày hôm sau sang nhà chó Spike chơi, mèo Tôm cứ lặp đi lặp lại các ngày như
vậy. Chuột Jerry biết được lịch trình của mèo Tôm nên cứ đến ngày mèo Tôm sang nhà chó Spike
chơi thì chuột Jerry sang nhà mèo Tôm lấy đi một nửa số thóc mà ngày hôm trước mèo Tôm thu
hoạch được (nếu số thóc mèo Tôm thu hoạch là số lẻ - giả sử là \(X\) thì số thóc chuột Jerry lấy là một nửa của \((X − 1)\)).

Biết rằng, mèo Tôm lần đầu tiên sẽ thu hoạch được \(K\) hạt thóc, và mỗi lần thu hoạch sau đó sẽ
bị giảm \(1\) hạt thóc (lần thứ hai thu hoạch \(K − 1\) hạt thóc, lần thứ ba thu hoạch \(K − 2\) hạt thóc,...) và đến khi thu hoạch được \(1\) hạt thóc thì sẽ không bị giảm nữa.

Mèo Tôm là một con mèo rất kém tính toán, mèo Tôm muốn biết sau ít nhất bao nhiêu ngày thì
trong nhà mèo Tôm có tối thiểu \(M\) hạt thóc. Em hãy lập trình để tính toán giúp mèo Tôm.

Yêu cầu: Cho ba số tự nhiên \(N\), \(M\) và \(K\). Hỏi thời điểm đầu tiên mà ở trong nhà mèo Tôm có tối thiểu \(M\) hạt thóc.

Input

Nhập vào ba dòng tương ứng là ba số tự nhiên \(N\), \(M\) và \(K\) \((1 ≤ N, M, K ≤ 10^9)\); \(M > N\).

Output

Ghi ra một số là kết quả của bài toán.

Example

6
22
10

5

5
8
2

5

Scoring

• Nếu chương trình chạy đúng những trường hợp \(N\), \(M\), \(K\) ≤ \(10^4\), thí sinh sẽ được \(60\) điểm;

• Nếu chương trình chạy đúng những trường hợp \(N\), \(M\), \(K\) ≤ \(10^9\), thí sinh sẽ được \(100\) điểm