Giải bài trực tuyến

Quốc gia Inforland mới dành được độc lập. Giờ là lúc thiết kế quốc kỳ cho đất nước!

Theo dự kiến, quốc kỳ sẽ có dạng hình vuông được chia làm lưới N x N ô vuông nhỏ (các bạn đã từng thấy quốc kỳ có 3 sọc ngang hoặc 3 sọc dọc, nhưng chắc hẳn chưa nhìn thấy loại quốc kỳ mới này bao giờ). Mỗi ô vuông sẽ được tô bằng một trong K màu truyền thống của đất nước. Lá cờ này chỉ được tô một mặt, mặt còn lại để trống. Vì vậy, bạn chỉ cần quan tâm đến mặt trước của lá cờ.

Những người đứng đầu quốc gia Inforland đang băn khoăn không biết có bao nhiêu lựa chọn cho quốc kỳ của mình nếu một số điều kiện được đưa ra. Bạn hãy giúp họ giải quyết bài toán trên. Lưu ý, đây là bài tập may mắn nên ngoài kết quả của bài toán, các bạn cần phải in ra một con số may mắn ở dòng đầu tiên. Con số may mắn sẽ là 1, 2 hoặc 3. Bộ test sẽ đảm bảo rằng mỗi con số sẽ ứng với đúng một loại test (dễ/trung bình/khó) và mỗi loại test sẽ có số điểm như nhau. Hình thức chấm vẫn là so file, nghĩa là bạn chỉ được điểm cho một test nếu con số may mắn bạn in ra trùng với con số ở kết quả mẫu.

• Với bộ test dễ, N = 3 và 2 lá cờ được coi là giống nhau nếu màu của từng ô tương ứng (cùng vị trí) là giống nhau. Số màu truyền thống của đất nước K thỏa mãn: 50 <= K <= 1000.

• Với bộ test trung bình, N = 3 và 1 <= K <= 6. Hai lá cờ được coi là giống nhau nếu sau một số phép xoay 90 độ, màu của từng ô tương ứng (cùng vị trí) là giống nhau.

• Với bộ test khó, N = 4 và 1 <= K <= 50. Hai lá cờ được coi là giống nhau nếu sau một số phép xoay 90 độ, màu của từng ô tương ứng (cùng vị trí) là giống nhau.

Ở ví dụ bên dưới, đó là một test dễ (do N = 3 và 50 <= K) ứng với con số may mắn 3. Tuy nhiên, số 3 có thể không tương ứng với các test dễ ở bộ test chính thức.

Input

Gồm một dòng duy nhất ghi 2 số N, K.

Output

Dòng đầu ghi con số may mắn bạn chọn.
Dòng sau ghi ra phần dư khi chia kết quả tìm được cho 10007.

Example

Input:
3 50

Output:
3
1798