Bạn được cung cấp một số nguyên n. Trên mỗi bước, bạn có thể trừ một trong các chữ số khỏi số. Cần thực hiện bao nhiêu bước để số đó bằng 0?

Đầu vào

Dòng duy nhất chứa số nguyên n

Giới hạn

1<=n<=10^6

Đầu ra

In ra số bước tối thiểu

Ví dụ :

Input 01

27

Output 01

5

Giải thích test :

Các bước thực hiện : 27→20→18→10→9→0

Bạn biết rằng một mảng có n số nguyên chỉ gồm các số từ 1 đến m và độ lệch giữa 2 phần tử liền kề trong mảng không được vượt quá 1 đơn vị.

Bài toán đặt ra đó là cho bạn một mảng trong đó một số giá trị trong mảng chưa được xác định giá trị, nhiệm vụ của bạn là đếm số mảng phù hợp với mô tả, đó là các số liền kề trong mảng không lệch nhau quá 1 đơn vị và các giá trị trong mảng chỉ được nằm trong đoạn từ 1 tới m.

Đầu vào

Dòng nhập đầu tiên có hai số nguyên n và m: kích thước mảng và giới hạn trên cho mỗi giá trị.

Dòng tiếp theo có n số nguyên a1, a2,…, an: nội dung của mảng. Giá trị 0 biểu thị một giá trị không xác định.

Giới hạn

1≤n≤10^5

1≤m≤100

0≤a[i]≤m

Đầu ra

In ra số lượng mảng phù hợp sau khi chia dư cho 1e9 + 7

Ví dụ :

Input 01

3 5
2 0 2

Output 01

3

Giải thích test :

Các mảng có thể thỏa mãn : [2, 1, 2], [2, 2, 2], [2, 3, 2]

Nhiệm vụ của bạn là đếm số cách các số 1,2,…, n có thể chia thành hai tập có tổng bằng nhau.

Các phần tử trong tập không xét đến thứ tự Ví dụ, nếu n = 7, có 4 nghiệm: {1,3,4,6} và {2,5,7}. {1,2,5,6} và {3,4,7}. {1,2,4,7} và {3,5,6}. {1,6,7} và {2,3,4,5}.

Đầu vào

Dòng duy nhất chứa số nguyên dương n

Giới hạn

1<=n<=500

Đầu ra

In ra kết quả sau khi chia dư với 10^9 + 7

Ví dụ :

Input 01

7

Output 01

4

Cho một hình chữ nhật a × b, nhiệm vụ của bạn là cắt nó thành các hình vuông.

Trên mỗi lần cắt, bạn có thể chọn một hình chữ nhật và cắt nó thành hai hình chữ nhật sao cho tất cả độ dài các cạnh vẫn là số nguyên. Số lần di cắt tối thiểu có thể là bao nhiêu?

Đầu vào

Dòng duy nhất chứa 2 số nguyên a và b.

Giới hạn

1<=a,b<=500

Đầu ra

In ra số lần cắt tối thiểu

Ví dụ :

Input 01

3 5

Output 01

3

Hệ số nhị phân và hệ thập lục phân (16) là 2 hệ số yêu thích của 28Tech, ngoài ra 28Tech cũng yêu thích những số lớn nữa. Bây giờ 28Tech cung cấp cho bạn 1 mảng 2 chiều nhị phân cỡ N hàng và N cột bao gồm các số 0 và 1, bạn xuất phát từ ô (1, 1) và tìm đường đi tới ô (N, N), tại mỗi lần di chuyển bạn được đi từ ô hiện tại xuống dưới hoặc sang phải. Nghĩa là nếu bạn đang ở ô (i, j) thì bạn có thể đi xuống ô (i + 1, j) hoặc ô (i, j + 1).

Trên đường đi đó bạn sẽ lấy các số 0 hoặc 1 tại ô bạn đi qua và khi đó bạn sẽ tạo được một số nhị phân có độ dài 2*N - 1, nhiệm vụ của bạn là hãy tìm cách đi tạo ra số nhị phân lớn nhất và in ra nó dưới dạng hệ số 16.

Ví dụ trong mảng 2 chiều này cách đi tạo ra số nhị phân lớn nhất là 1111011 tương ứng với số 123 trong hệ thập phân và 7B trong hệ 16, vì thế bạn cần in 7B

Đầu vào

Dòng đầu tiên chứa số N

N dòng tiếp theo mỗi dòng chứa N số của ma trận

Giới hạn

1<=N<=100

Đầu ra

In ra số nhị phân lớn nhất tạo thành ở hệ 16.

Ví dụ :

Input 01

8
1 0 0 1 0 0 0 0 
0 0 0 0 0 1 1 0 
0 1 1 0 0 0 1 1 
1 1 0 1 0 0 0 0 
1 1 0 0 0 0 1 1 
0 1 1 0 1 0 0 1 
0 1 1 0 1 1 0 0 
0 1 1 1 1 0 0 1

Output 01

4FF9

Input 02

5
1 1 0 0 0 
1 1 0 0 0 
1 1 0 0 0 
0 1 0 1 0 
1 0 0 1 1

Output 02

1F7