Bài tập

Chủ trại có \(N\) con trâu, con thứ \(i\) nặng \(w_i\). Ông muốn chia toàn bộ đàn thành hai nhóm (một nhóm có thể rỗng) sao cho chênh lệch giữa tổng cân nặng của hai nhóm là nhỏ nhất. Hãy tìm chênh lệch nhỏ nhất đó.

Input

• Dòng 1: số nguyên \(N\).
• Dòng 2: \(N\) số nguyên \(w_1, \dots, w_N\).

Output

• In ra chênh lệch nhỏ nhất (là một số không âm).

Constraints

• \(1 \le N \le 38\)
• \(1 \le w_i \le 10^9\)

Sample Input

6
8 3 5 9 2 6

Sample Output

1

Explanation

Tổng là \(33\); chia thành \(\{8,9\}\) (17) và \(\{3,5,2,6\}\) (16), chênh lệch 1.

Đội văn nghệ có \(M\) bạn nam và \(N\) bạn nữ. Đội muốn chia thành nhiều tổ nhất có thể sao cho mọi bạn đều thuộc một tổ, các tổ có số nam bằng nhau và số nữ bằng nhau (mỗi tổ có cả nam lẫn nữ).

Hãy cho biết số tổ nhiều nhất, và khi đó mỗi tổ có bao nhiêu nam, bao nhiêu nữ.

Input

Một dòng chứa hai số nguyên \(M\) và \(N\).

Output

In ra ba dòng đúng theo mẫu:

• So to: và số tổ,
• So nam moi to: và số nam mỗi tổ,
• So nu moi to: và số nữ mỗi tổ.

Constraints

• \(1 \le M, N \le 10^{12}\)

Sample Input

24 36

Sample Output

So to: 12
So nam moi to: 2
So nu moi to: 3

Explanation

Số tổ nhiều nhất là \(\gcd(24, 36) = 12\); mỗi tổ có \(24/12 = 2\) nam và \(36/12 = 3\) nữ.

Cho một xâu \(s\) khác rỗng chỉ gồm các chữ số. Ta cắt xâu thành một số nhóm liên tiếp (mỗi chữ số thuộc đúng một nhóm, giữ nguyên thứ tự) sao cho tổng các chữ số của mỗi nhóm không vượt quá tổng các chữ số của nhóm ngay bên phải nó, tức là dãy tổng các nhóm là không giảm từ trái sang phải. Việc không cắt gì (cả xâu là một nhóm) cũng được tính là một cách chia hợp lệ.

Ví dụ với \(s = 635\): chia thành \([635]\) (tổng \(14\)) hoặc \([6][35]\) (tổng \(6 \le 8\)) là hợp lệ, còn \([63][5]\) (tổng \(9 > 5\)) và \([6][3][5]\) (tổng \(6 > 3\)) thì không. Vậy có \(2\) cách.

Hãy đếm số cách chia hợp lệ của mỗi xâu. Hai cách khác nhau nếu tập vị trí cắt khác nhau. Vì kết quả có thể rất lớn, in ra phần dư khi chia cho \(10^9 + 7\).

Input

Dữ liệu gồm nhiều bộ test, mỗi bộ test là một xâu trên một dòng. Kết thúc bằng một dòng chứa đúng từ bye (dòng này không phải bộ test).

Output

Với bộ test thứ \(k\) (đánh số từ 1), in ra một dòng có dạng k. n, trong đó \(n\) là số cách chia hợp lệ lấy modulo \(10^9 + 7\).

Constraints

• Số bộ test không quá \(20\).
• Mỗi xâu có độ dài từ \(1\) đến \(200\) và chỉ gồm các chữ số thập phân.

Sample Input

2213
1234
5
40
bye

Sample Output

1. 5
2. 6
3. 1
4. 1

Explanation

Xâu 2213 có \(5\) cách: \([2213]\), \([2][213]\), \([22][13]\), \([2][2][13]\), \([2][21][3]\). Xâu 5 chỉ có \(1\) cách. Xâu 40: cách \([4][0]\) không hợp lệ vì \(4 > 0\) nên chỉ còn cách giữ nguyên cả xâu, được \(1\) cách.

Một số nguyên dương \(n\) được gọi là số chia hết tổng chữ số nếu \(n\) chia hết cho tổng các chữ số trong biểu diễn thập phân của nó. Chẳng hạn \(36\) có tổng chữ số là \(9\) và \(36 = 4 \cdot 9\) nên thỏa mãn, còn \(25\) có tổng chữ số \(7\) và không chia hết cho \(7\) nên không thỏa mãn.

Cho số nguyên dương \(n\). Hãy kiểm tra \(n\) có thỏa mãn tính chất trên hay không.

Input

• Một dòng chứa số nguyên dương \(n\).

Output

• In ra 1 nếu \(n\) thỏa mãn, ngược lại in ra 0.

Constraints

• \(1 \le n \le 10^{18}\)

Sample Input 1

36

Sample Output 1

1

Sample Input 2

25

Sample Output 2

0