#P3851. 2048

    ID: 3042 传统题 2000ms 64MiB 尝试: 187 已通过: 55 难度: 6 上传者: 标签>CF2000提高不变量分析补集计数分组背包计数 DP阶乘逆元预处理滚动数组By镇海中学

2048

2048

Problem Description

Teacher Mai is addicted to game 2048. But finally he finds it's too hard to get 2048. So he wants to change the rule: You are given some numbers. Every time you can choose two numbers of the same value from them and merge these two numbers into their sum. And these two numbers disappear meanwhile. If we can get 2048 from a set of numbers with this operation, Teacher Mai think this multiset is good. You have n numbers, A 1 ,...,A n . Teacher Mai ask you how many subsequences of A are good. The number can be very large, just output the number modulo 998244353.

Input

There are multiple test cases, terminated by a line "0". For each test case, the first line contains an integer n (1<=n<=10^5), the next line contains n integers a i (0<=a i <=2048).

Output

For each test case, output one line "Case #k: ans", where k is the case number counting from 1, ans is the number module 998244353.

Sample Input

4
1024 512 256 256
4
1024 1024 1024 1024
5
1024 512 512 512 1
0

Sample Output

Case #1: 1
Case #2: 11
Case #3: 8

Hint

In the first case, we should choose all the numbers. In the second case, all the subsequences which contain more than one number are good.

Author

xudyh

Source

2014 Multi-University Training Contest 8