Tủ Quần Áo Kỳ Diệu

Điểm: 5,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Nastya có một chiếc tủ quần áo kỳ diệu. Vào cuối mỗi tháng, số váy trong tủ tăng lên gấp đôi (số váy cuối tháng bằng hai lần số váy đầu tháng).

Tuy nhiên, ngay sau khi nhân đôi, tủ sẽ ăn mất đúng một chiếc váy với xác suất $50 %$ (nếu trong tủ không còn chiếc váy nào thì không có gì để ăn). Điều này xảy ra ở mọi tháng trừ tháng cuối cùng trong năm — tháng cuối cùng chỉ nhân đôi mà thôi.

Một năm ở vương quốc nơi Nastya sống dài đúng $k + 1$ tháng. Ban đầu tủ có $x$ chiếc váy. Hãy tính kỳ vọng số váy trong tủ sau một năm, lấy theo modulo $10^{9} + 7$ (giá trị này luôn là số nguyên).

Dữ liệu vào

Một dòng chứa hai số nguyên $x$ và $k$ .

Dữ liệu ra

Một số nguyên duy nhất — kỳ vọng số váy sau một năm, lấy modulo $10^{9} + 7$ .

Ràng buộc

$0 \leq x, k \leq 10^{18}$

Ví dụ

Input	Output	Giải thích
2 0	4	Năm chỉ có $1$ tháng (tháng cuối), tủ chỉ nhân đôi: $2 \cdot 2 = 4$ .
2 1	7	Sau tháng $1$ : số váy là $3$ với xác suất $1 / 2$ , là $4$ với xác suất $1 / 2$ . Sau tháng $2$ (nhân đôi): $6$ hoặc $8$ , mỗi cái xác suất $1 / 2$ . Kỳ vọng $= (6 + 8) / 2 = 7$ .
3 2	21	Kỳ vọng sau tháng $1$ là $5.5$ , sau tháng $2$ là $10.5$ , sau tháng $3$ (nhân đôi) là $21$ .
0 24	0	Tủ rỗng nên không có gì để nhân đôi hay ăn.

Bình luận

Không có bình luận tại thời điểm này.