Bài tập

Trong một công ty công nghệ lớn, bạn được giao nhiệm vụ tổ chức một hội thảo chuyên đề cho \(N\) nhân viên. Mỗi nhân viên được đánh giá bằng một chỉ số đặc biệt gọi là độ tin cậy (\(a_i\)), biểu thị khả năng thực hiện các nhiệm vụ quan trọng của họ.

Nhiệm vụ của bạn là chia \(N\) nhân viên thành hai nhóm Group A và Group B, với các yêu cầu sau:

• Mỗi nhân viên thuộc đúng một nhóm.
• Sự chênh lệch về tổng độ tin cậy giữa hai nhóm là nhỏ nhất có thể.

Hãy tìm cách phân chia tối ưu và báo cáo giá trị độ chênh lệch nhỏ nhất cũng như số lượng cách phân chia đạt được kết quả này.

Input

Dữ liệu đầu vào gồm:

• Dòng đầu chứa một số nguyên \(N\) \((2 \leq N \leq 32)\), là số nhân viên.
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \ldots, a_N\) \((1 \leq a_i \leq 10^9)\), là độ tin cậy của các nhân viên.

Output

In ra hai số nguyên \(u\) và \(v\):

• \(u\): độ chênh lệch nhỏ nhất giữa tổng độ tin cậy của hai nhóm.
• \(v\): số lượng cách phân chia đạt được độ chênh lệch nhỏ nhất.

Example

5
1 5 6 7 8

1 3

Để tăng cường bảo mật, Thám tử K quyết định rằng các chuỗi nhị phân không được phép có hai số \(1\) nào đứng kề nhau (ví dụ: \(11\) bị cấm). Hãy sử dụng đệ quy để liệt kê tất cả các chuỗi nhị phân có độ dài \(N\) thỏa mãn điều kiện an toàn này.

Input

Một số nguyên dương \(N\) (\(1 \leq N \leq 15\)).

Output

In ra tất cả các chuỗi nhị phân thỏa mãn, mỗi chuỗi trên một dòng, theo thứ tự từ điển tăng dần.

Example

1

0
1

2

00
01
10

3

000
001
010
100
101

Trong một sứ mệnh không gian đặc biệt, trung tâm điều khiển trái đất cần thiết lập một giao thức mới để truyền dữ liệu về từ vệ tinh. Dữ liệu được chia thành các gói nhỏ, được biểu diễn bằng một dãy số nguyên không âm \(a(0), a(1), \dots, a(n)\).

Tuy nhiên, hệ thống mã hóa sử dụng một dạng năng lượng đặc biệt, trong đó chi phí để truyền bit \(i\) là \(a(i) \cdot 2^i\) đơn vị năng lượng. Vì vệ tinh chỉ có thể phát tín hiệu trong thời gian ngắn, tổng chi phí truyền phải không vượt quá mức năng lượng cho phép, cụ thể là:

Bạn được yêu cầu xác định có bao nhiêu dãy \((a(0), a(1), \dots, a(n))\) thỏa mãn điều kiện trên. Mỗi \(a(i)\) là một số nguyên không âm.

Input

• Một dòng duy nhất chứa số nguyên \(n\) \((0 \leq n \leq 249)\).

Output

• In ra một số nguyên duy nhất --- số dãy thỏa mãn điều kiện, lấy phần dư theo \(10^9 + 7\).

Example

5

25510

35

490154274

Scoring

\begintabularc c l
\hline
Subtask & Điểm & Ràng buộc

\hline
1 & 25 & \(n \leq 10\)

2 & 75 & Không có ràng buộc bổ sung

\hline
\endtabular

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