Giả thuyết Goldbach do nhà toán học người Đức Christian Goldbach (1690-1764) nêu ra vào năm 1742 trong một lá thư gửi tới Leonhard Euler, là một trong những bài toán lâu đời và nổi tiếng còn chưa giải được trong lý thuyết số nói riêng và toán học nói chung.

Giả thuyết phỏng đoán rằng: "Mọi số tự nhiên chẵn lớn hơn 2 có thể biểu diễn bằng tổng của hai số nguyên tố."

Hẳn là các bạn đều biết đến số nguyên tố, là số mà ước của nó chỉ có 1 và chính nó.

Sau khoảng thời gian Hiếu tìm tòi về giả thuyết này, cậu ta phát hiện ra một điều rằng : "Tất cả các số nguyên dương lớn hơn 1 đều có thể biểu diễn bằng tổng các số nguyên tố nhỏ hơn hoặc bằng nó"

Nếu các bạn muốn biết Hiếu phát hiện ra điều này như nào, thì dễ lắm !!!

Hiếu đố các bạn tìm ra được một cách biểu diễn số nguyên dương N bất kỳ lớn hơn 1 thành tổng các số nguyên tố mà số lượng số các bạn sử dụng là nhiều nhất.

Input Format

• 1 dòng chứa số nguyên ~N~ ( ~2 ≤ N ≤ 1000 ~ )

Output Format:

• Dòng thứ nhất in ra số lượng số các bạn dùng
• Dòng thứ hai in ra các số các bạn dùng từ bé đến lớn

Sample Input:

7

Sample output:

3
2 2 3

Toán học luôn có sự kì diệu đối với những ai hứng thú với nó. Chúng ta thường biểu diễn các số dưới dạng thập thân hay nói cách khác, cơ số 10

Nhưng chúng ta có thể viết các số đó dưới dạng cơ số số nguyên dương như 2, 6, ... Thậm chí cả phân số !

Vậy 1 số nguyên dương ~N~ ở dạng thập phân được biểu diễn sang cơ số của một phân số bất kì thì nó sẽ được biểu diễn như nào?

Dữ liệu được đảm bảo luôn có kết quả !

Input Format

• 1 dòng chứa 3 số nguyên dương ~N~ ~x~ ~y~ ở dạng thập phân ( ~10 ≤ N ≤ 10^{6} ~, ~2 ≤ x ≤ 10 ~, ~1 ≤ y ≤ 10 ~)

Output Format:

• In ra ~N~ ở dạng cơ số ~\frac{x}{y}~

Sample Input:

783 7 1

Sample output:

2166

Sample Input:

265 7 3

Sample output:

64366

Giải thích

• ~2 * 7^{3} + 1 * 7^{2} + 6 * 7^{1} + 6 * 7^{0} = 783 ~
• ~6 * (\frac{7}{3}) ^ {4} + 4 * (\frac{7}{3}) ^ {3} + 3 * (\frac{7}{3}) ^ {2} + 6 * (\frac{7}{3}) ^ {1} + 6 * (\frac{7}{3}) ^ {0} = 265~

Hiếu là cậu học trò ngông nên thầy giáo cho cậu một bài toán đơn giản được phát biểu : Cho số nguyên dương không âm ~N~. Tính số chữ số của ~N!~.

Tuy nhiên Hiếu lại không làm được, bảo hôm sau sẽ giải được. Bạn hãy giúp Hiếu để được oai lần nữa nhé ?

Input Format

• 1 dòng chứa số nguyên ~N~ ( ~1 ≤ N ≤ 10^{9} ~ )

Output Format:

• In ra dạng rút gọn của ~N~

Sample Input:

4

Sample output:

2

Sample Input:

2024

Sample output:

5814

Giải thích

• ~4!~ = ~24~ -> ~2~

"Ai chắp cánh cho đôi chim bay về tổ

Ai dẫn lối cho đôi bạn trẻ của chúng tôi

Tôi nguyện làm cơn gió chiều

Để thổi bùng lên ngọn lửa tình yêu !!!"

Ngân nga thế thôi !! Hiếu tỉnh dậy khỏi cơn mê làm MC.

Cậu ta luôn có niềm đam mê với toán, vì vậy cậu ta chỉ học mỗi toán dẫn tới các môn khác điểm thấp và trượt đại học. Cậu phải làm việc chân tay, lát nền gạch để kiếm sống

Việc chân tay nhưng không cản được đam mê của Hiếu, một ngày cậu ta tự đặt ra 1 bài toán để đố bạn :

Cho 1 hành lang ~2~ x ~N~ được lát bằng các viên gạch ~1~x~2~, ~2~x~2~. Giả sử không có viên nào bị cắt hay trùng lặp và không được đặt 2 viên ~2~x~2~ cạnh nhau

Vậy có bao nhiêu cách lát hành lang này. Lưu ý: Đặt ~1~x~2~ ngang được tính khác trường hợp với 1x2 dọc

Do kết quả có thể lớn nên bạn hãy lấy kết quả khi chia dư cho ~10^{9}+7~

Input Format

• 1 dòng chứa 1 số nguyên dương ~N~( ~10 ≤ N ≤ 10^{6} ~)

Output Format:

• In ra số cách lát hành lang ~2~ x ~N~ thỏa mãn đề bài

Sample Input:

5

Sample output:

19