Sau khi giúp Barca giành cú ăn ba Cúp nhà Vua, La Liga và UEFA Champions League, đồng thời cũng có giành được danh hiệu quả bóng vàng lần thứ 5 trong sự nghiệp. Giá trị chuyển nhượng của Lionel Messi tăng lên một cách nhanh chóng. Khi kì chuyển nhượng bắt đầu, giá trị của Messi là X và cứ mỗi ngày trôi qua, giá trị của anh ấy tăng lên X lần so với ngày trước đó. Về phía Paris Saint-Germain (PSG) thì luôn muốn có được sự phục vụ của Messi. Ban lãnh đạo của PSG quyết định phải mua được Messi bằng mọi giá. Họ quyết định sẽ sắp xếp mọi việc trong Y ngày: hợp đồng, lương thưởng, phí chuyển nhượng, vị trí thi đấu và cũng là thời gian để PSG bán một số cầu thủ khác để lấy kinh phí mua lại Messi.

Ban lãnh đạo muốn biết rằng sau Y ngày kể từ khi kì chuyển nhượng bắt đầu, giá của Messi sẽ là bao nhiêu để họ có thể chuẩn bị trước. Và nhiệm vụ này được giao cho bạn - nhân viên kế toán của câu lạc bộ.

Tuy nhiên, theo luật cân bằng tài chính mới của UEFA, để tránh việc giá của một cầu thủ bị đẩy lên quá cao so với mặt bằng chung. UEFA quyết định rằng giá trị của mỗi cầu thủ không được phép vượt qua 10⁹+7, nếu vượt qua con số này, giá trị của cầu thủ đó sẽ được quy về là phần dư sau khi chia cho 10⁹+7.

Dữ liệu nhập: Một dòng duy nhất chứa 2 số nguyên dương X, Y (1 ≤ X, Y ≤ 10^1000000, X nguyên tố cùng nhau với 10⁹+7).

Dữ liệu nhập: Với mỗi test case xuất ra giá trị của Messi tại ngày thứ Y.