Cô Khong đang tổ chức một cuộc thi với \(x\) người tham gia và muốn tặng mỗi người một túi bánh quy. Có \(k\) loại bánh quy khác nhau, được đánh số từ \(0\) đến \(k-1\). Mỗi chiếc bánh quy loại \(i\) (\(0 \le i \le k-1\)) có độ ngon bằng \(2^i\). Trong tủ thức ăn, cô Khong có \(a[i]\) chiếc bánh quy loại \(i\); số lượng này có thể bằng không.

Mỗi túi có thể chứa không hoặc nhiều chiếc bánh quy của mỗi loại. Tổng số bánh quy loại \(i\) trong tất cả các túi không được vượt quá \(a[i]\). Tổng độ ngon của tất cả bánh quy trong một túi được gọi là tổng độ ngon của túi đó.

Hãy giúp cô Khong tìm số lượng giá trị \(y\) khác nhau sao cho có thể đóng gói \(x\) túi bánh quy, mỗi túi có tổng độ ngon bằng \(y\).

Chi tiết cài đặt

Bạn cần cài đặt hàm C++ sau:

long long count_tastiness(long long x, std::vector<long long> a);

• \(x\): số túi bánh quy cần đóng gói.
• \(a\): mảng có độ dài \(k\). Với mỗi \(0 \le i \le k-1\), \(a[i]\) là số chiếc bánh quy loại \(i\) trong tủ thức ăn.
• Hàm phải trả về số lượng giá trị \(y\) khác nhau sao cho cô Khong có thể đóng gói \(x\) túi bánh quy, mỗi túi có tổng độ ngon bằng \(y\).
• Hàm được gọi tổng cộng \(q\) lần; các giá trị cho phép của \(q\) được nêu trong phần Ràng buộc và Phân nhóm. Mỗi lần gọi phải được xử lý như một kịch bản riêng biệt.

Ràng buộc

• \(1 \le k \le 60\).
• \(1 \le q \le 1000\).
• \(1 \le x \le 10^{18}\).
• \(0 \le a[i] \le 10^{18}\) (\(0 \le i \le k-1\)).

Với mỗi lần gọi count_tastiness, tổng độ ngon của tất cả bánh quy trong tủ thức ăn không vượt quá \(10^{18}\):

Phân nhóm

Ví dụ

Các ví dụ dưới đây mô tả lời gọi hàm và giá trị trả về.

count_tastiness(3, [5, 2, 1])

5

    Chẳng hạn, để đóng gói $3$ túi, mỗi túi có tổng độ ngon $3$, cô có thể đóng gói:


    - một túi chứa ba chiếc bánh quy loại $0$;
    - hai túi, mỗi túi chứa một chiếc bánh quy loại $0$ và một chiếc bánh quy loại $1$.

    Vì có $5$ giá trị $y$ có thể có, hàm phải trả về $5$.

    ![Hình minh họa ví dụ Packing Biscuits](https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_1_b744a53e.png)

count_tastiness(2, [2, 1, 2])

6

    Vì có $6$ giá trị $y$ có thể có, hàm phải trả về $6$.

Dữ liệu vào

Trình chấm mẫu đọc dòng đầu tiên chứa số nguyên \(q\). Sau đó là \(q\) cặp dòng, mỗi cặp mô tả một kịch bản theo định dạng:

k x
a[0] a[1] ... a[k-1]

Dữ liệu ra

Trình chấm mẫu in \(q\) dòng. Dòng \(i\) (\(1 \le i \le q\)) chứa giá trị trả về của count_tastiness cho kịch bản thứ \(i\) trong dữ liệu vào.

Nguồn

IOI 2020, Ngày 2 — Packing Biscuits (biscuits). Đề chính thức tiếng Anh và bản dịch tiếng Việt.