题目描述

注意：在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++ 11
• C++ 11 (Clang)
• C++ 11 (NOI)
• C++ 17
• C++ 17 (Clang)

Khong 阿姨在组织一场有 $x$ 位选手参加的竞赛，她打算给每位选手一袋饼干。总共有 $k$ 种不同类型的饼干，编号为从 $0$ 到 $k - 1$。类型为 $i$（$0 \le i \le k - 1$）的每块饼干都有一个口味值 $2^i$。在 Khong 阿姨的食品储藏室里，有 $a_i$（有可能为 $0$）块类型为 $i$ 的饼干。

对每种类型的饼干，Khong 阿姨在每个袋子都会装上 $0$ 或者多块。所有袋子里面类型为 $i$ 的饼干的总块数不能超过 $a_i$。一个袋子里面所有饼干的口味值的总和，被称为这袋饼干的总口味值。

请帮 Khong 阿姨算一下，究竟存在多少不同的 $y$ 值，使得她可以装出 $x$ 袋饼干，而且每袋饼干的总口味值都等于 $y$。

实现细节

你需要实现以下函数：

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

• $x$：需要装的饼干袋的数量。
• $a$：长度为 $k$ 的数组。对 $0 \le i \le k - 1$，$a_i$ 表示在食物储藏室里类型为 $i$ 的饼干数量。
• 此函数应当返回不同 $y$ 值的数目，使得阿姨可以装出 $x$ 袋饼干，且每袋饼干的总口味值都为 $y$。
• 此函数会被调用 $q$ 次（对于允许的 $q$ 值，详见约束条件和子任务部分）。每次调用应当被看成是独立的场景。

评测程序示例

评测程序示例将读取如下格式的输入数据。第一行包含一个整数 $q$。接下来是 $q$ 对这样的两行：它们按照下面的格式来描述一个单独的场景：

• 第一行：$k\ x$
• 第二行：$a_0\ a_1\ \ldots\ a_{k - 1}$

评测程序示例的输出结果的格式如下：

• 第 $i$ 行（$1 \le i \le q$）：count_tastiness 对于输入数据中第 $i$ 个场景的返回值。

3 3
5 2 1

5

3 2
2 1 2

6

数据范围与提示

对于全部数据，满足：

• $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$）
• 对于 count_tastiness 的每次调用，食物储藏室里所有饼干的口味值总和都不会超过 $10^{18}$。

详细子任务分值与附加限制如下表：