“2048” 玩家国际协会发布了 Division 2 的 2048 游戏规则。

Division 2 的玩家在开始时拥有一些数字（不仅限于 2 的幂）。每次他可以选择两个值相同的数字，并将这两个数字合并为它们的和。同时，这两个数字会消失。

如果他能通过此操作从一个数字集合中得到 2048，我们称该多重集为“获胜”的。

你有 $n$ 个数字 $A_1, \dots, A_n$。找出 $A$ 的子序列中有多少个是“获胜”的。答案可能非常大，请输出其对 998244353 取模的结果。

输入格式

输入包含不超过 70 个测试用例，以包含单个零的行结束。

对于每个测试用例，第一行包含一个整数 $n$ ($1 \le n \le 10^5$)。下一行包含 $n$ 个整数 $a_i$ ($0 \le a_i \le 2048$)。

输入文件大小不超过 5.5 MB。

输出格式

对于每个测试用例，输出一个整数，即问题的答案。

样例

输入格式 1

5
513 511 256 512 256

输出格式 1

0

输入格式 2

8
512 512 512 512 512 512 512 512

输出格式 2

163

输入格式 3

3
1024 256 512

输出格式 3

0