Cho 2 số nguyên dương \(n\) và \(k\).
Yêu cầu: In ra số thứ \(n\) chia hết cho \(k\) sau khi lấy dư cho \(1e9 + 7\).

INPUT

• Một dòng duy nhất chứa lần lượt 2 số nguyên dương \(n,k (1 \leq n,k \leq 10^{18})\)

OUTPUT

• In ra một số nguyên duy nhất là kết quả bài toán.

Example

3 2

4

Giới hạn

• Có 20% số điểm ứng với \(n,k \leq 10^6\)
• Có 80% số điểm còn lại không có giới hạn gì thêm.

Hãy trả lời \(t\) câu hỏi có dạng sau: Cho hai số thực có tối đa 16 chữ số sau dấu phẩy thập phân, tính tổng của hai số đó

Dữ liệu đầu vào

• Dòng đầu tiên chứa số \(t\) \((1 \leq t \leq 1000)\)
• \(t\) dòng tiếp theo, mỗi dòng chứa hai số thực có không quá 16 chữ số thập phân

Định dạng đầu ra

• In ra \(t\) dòng là đáp án tương ứng của mỗi câu hỏi, không gồm chữ số 0 thừa ở đuôi

Ví dụ

2
2 3
1.2 2.3

5
3.5

Thầy Minh tổ chức buổi phát thưởng cho các học sinh đạt giải trong kỳ thi học sinh giỏi môn Tin. Thầy có X chiếc bút và Y quyển tập, thầy sẽ phát hết các phần thưởng cho các bạn học sinh và mong muốn số chiếc bút và số quyển tập được chia đều cho các bạn.

Yêu cầu: Cho hai số nguyên \(X\) và \(Y\). Hãy tìm tất cả các cách phát quà thỏa mãn điều kiện của thầy Minh.

Dữ liệu

Vào từ file văn bản GIFTS.INP gồm một dòng chứa \(2\) số nguyên dương \(X, Y\).

Dữ liệu đảm bảo: \(1 \le X, Y \le 10^{14}\).

Kết quả

Ghi vào file văn bản GIFTS.OUT một số nguyên là số cách phát quà thỏa điều kiện đề bài.

Ràng buộc

• Subtask 1: \(60\%\) số test ứng với \(1 \le X, Y \le 10^6\)
• Subtask 2: \(40\%\) số test không có ràng buộc gì thêm.

Ví dụ

4 6

2