Khu vực sinh sống của một con kiến là một ma trận hình chữ nhật kích thước nxm ô. Mỗi ô của ma trận có thể là ô trống được kí hiệu bời kí tự '1' hoặc có thể là ô cấm kí hiệu bởi kí tự '0'. Con kiến đang ở tại ô (1,1) của ma trận. Nó cần tìm con đường di chuyển với số bước ít nhất đến ô (n, m) để lấy thức ăn. Theo bạn, con kiến có bao nhiêu đường đi như thế để di chuyển đến ô (n, m) và số bước ít nhất là bao nhiêu? Biết rằng, mỗi bước di chuyển từ ô (i, j), kiến có thể đi tới 4 ô chung cạnh không phải là ô cấm và tất nhiên kiến không được đi ra ngoài ma trận.

Dữ liệu vào: Đọc từ tệp văn bản ANT.INP gồm:

• Dòng đầu tiên chứa hai số nguyên n, m (2 ≤ n, m ≤ 10^3) lần lượt là số dòng, số cột của ma trận.

• n dòng tiếp theo: dòng thứ i chứa một xâu độ dài m gồm hai loại kí tự '1' hoặc '0' mô tả dòng thứ i của ma trận.

• Dữ liệu vào đảm bảo con kiến luôn tìm được đường đi lấy thức ăn.

Kết quả ra: Ghi vào tệp văn bản ANT.OUT gồm:

Dòng 1: Ghi một số nguyên là phần dư của số đường đi cần tìm chia cho 10^8 + 7.

Dòng 2: Ghi một số nguyên là số bước ít nhất mà kiến phải đi để lấy thức ăn.

Ràng buộc:

• Các test tương ứng với 20% số điểm có : 2 ≤ n x m <= 10.

• Các test tương ứng với 40% số điểm có: 2 ≤ n, m ≤ 10^3.

• Các test tương ứng với 40% số điểm: Không có ràng buộc gì thêm.

Input 01:

3 3
101
111
011

Output 01:

2 
4

Giải thích: Có 2 đường đi từ ô (1,1) đến ô (3,3) với số bước ít nhất (4 bước)

Input 02:

2 2
11
01

Output 02:

1
2

Giải thích: Có 1 đường đi từ ô (1,1) đến ô (2,2) với số bước ít nhất (2 bước)