Bài tập

Viết chương trình nhập vào một chuỗi nhị phân \(S\) (độ dài tối đa 31). Hãy chuyển đổi chuỗi này thành số nguyên thập phân và in ra kết quả.

Input

Một dòng duy nhất chứa chuỗi nhị phân \(S\).

Output

Một dòng duy nhất chứa số nguyên thập phân tương ứng.

Example

11101

29

Nhập vào ba số nguyên a, b, c. Nếu a < 5 hoặc b > 10 hoặc c = 20, thì in ra "YES". Ngược lại in ra "NO".

Example

3 4 5

YES

2 4 20

YES

Ami rất thích sưu tập các con số đặc biệt. Theo cậu, một số càng "đơn giản" thì càng đẹp. Vì vậy, Ami chỉ quan tâm đến những số được tạo thành từ không quá \(K\) chữ số khác nhau.

Ví dụ:

• \(12222111\) chỉ sử dụng hai chữ số là \(1\) và \(2\), nên đẹp với \(K \ge 2\).
• \(505050\) chỉ sử dụng hai chữ số là \(0\) và \(5\).
• \(123456\) sử dụng sáu chữ số khác nhau.

Ami muốn tính tổng tất cả các số đẹp nằm trong đoạn \([L,R]\).

Yêu cầu. Cho ba số nguyên \(L\), \(R\) và \(K\). Hãy tính tổng các số trong đoạn \([L,R]\) mà sử dụng không quá \(K\) chữ số khác nhau.

Vì kết quả có thể rất lớn, chỉ cần in ra kết quả theo modulo \(998244353\).

\InputFile

Gồm một dòng chứa ba số nguyên

thỏa mãn

\OutputFile

In ra một số nguyên là tổng các số thỏa mãn điều kiện, lấy modulo \(998244353\).

\Examples

\beginexample
\exmp
10 50 2

1230

\exmp
1 2345 10

2750685

\exmp
101 154 2

2189

\endexample

\Note

Trong ví dụ thứ nhất, mọi số trong đoạn đều sử dụng không quá \(2\) chữ số khác nhau, nên đáp án chính là tổng các số từ \(10\) đến \(50\).

\endproblem

Bạn An đang chuẩn bị đi chơi tuy nhiên bạn sợ việc sử dụng tiền tài khoản đôi khi bị nghẽn mạng sẽ không chuyển được tiền đi xe, tiền mua các nhu yếu phẩm, mua quà, ... nên bạn nhờ cửa hàng B đổi cho mình \(n\) nghìn đồng tiền tài khoản thành tiền mặt. Để tiện cầm tiền mặt, bạn An nhờ cửa hàng B đổi tiền cho mình sao cho số tờ là nhỏ nhất có thể. Em hãy giúp cửa hàng B thực hiện công việc trên, biến rằng tiền Việt Nam có các mệnh giá : 1 nghìn đồng, 2 nghìn đồng, 5 nghìn đồng, 10 nghìn đồng, 20 nghìn đồng, 50 nghìn đồng, 100 nghìn đồng, 200 nghìn đồng, 500 nghìn đồng.

Input

Đọc từ tệp DT.INP gồm một số nguyên dương duy nhất \(n\) (\(n \le 10^9\)).

Output

Ghi vào tệp DT.OUT ghi theo cấu trúc sau :

Các dòng đầu trên mỗi dòng kê mệnh giá và số tờ tiền mặt : mệnh giá trước, số tờ sau (đặt cách nhau một dấu cách trống, các mệnh giá không có tờ nào thì không kê).

Dòng cuối cùng ghi tổng số tờ.

Example

1234

500 2
200 1
20 1
10 1
2 2
7