Nếu bạn là người đam mê đồ cổ, hẳn "cục gạch" 3510i không còn xa lạ gì. Đúng với miêu tả về một "cục gạch", chú dế này có kiểu dáng tương đối thô và nặng, cầm rất "đầm" tay, bàn phím nổi nhắn tin cực nhanh, cực thích, rung cực mạnh, sóng cực khỏe, loa cực to... Một tính năng nổi bật khác của “cục gạch” là tính bảo mật cực tốt, khi bật máy, máy sẽ yêu cầu người dùng nhập vào mật khẩu, nếu người dùng không nhập đúng mật khẩu chỉ còn cách ném nó như ném cục gạch. Bông may mắn được sở hữu một chiếc điện thoại như vậy. Bàn phím điện thoại có dạng như hình dưới bên phải. Để tạo mật khẩu và cho dễ nhớ Bông đã tạo ra mật khẩu bằng cách:

- Mật khẩu là một dãy các chữ số độ dài n;
- Bắt đầu bằng một chữ số khác số 0 và số 8;
- Chữ số tiếp theo được lựa chọn là chữ số nằm trong ô ở thế mã giao chân với ô đang chứa chữ số hiện tại.

Yêu cầu: cho n, hãy giúp Bông tính xem có bao nhiêu cách lựa chọn mật khẩu có độ dài bằng n theo cách nêu trên.

Input

- Gồm một dòng, chứa hai số nguyên dương  n, k (n<=???)

Output

- Gồm một dòng, chứa số cách lựa chọn mật khẩu có độ dài bằng n chia dư cho 10^k .