Counting Winning Card Combinations

You are given a deck of cards consisting of n types, numbered 1,2,...,n. There are C copies of each type (so a total of n×C cards), but you only have some drawn cards. The drawn count for each card type i is given as a non‐negative integer a[i] (with 0 ≤ a[i] ≤ C).

A valid pile can be formed in one of two ways:

• Three consecutive cards: (i, i+1, i+2).
• Three identical cards: (i, i, i).

A set of selected cards is called a winning combination if all the selected cards can be partitioned into several (possibly zero) valid piles. (Note that if no cards are selected, the empty set is considered valid.)

Two winning combinations are considered the same if for every card type the counts of selected cards are identical.

Your task is to count the number of ways to choose a sub-multiset (i.e. for each type choose some number between 0 and a[i]) from the drawn cards so that the chosen cards form a winning combination. Output the answer modulo 998244353.

Note: For instance, if n = 1 (so there is only one card type) then the only way to partition the selected cards is to form piles of three identical cards. In that case, the number of selected cards must be a multiple of 3.

inputFormat

The first line contains a single integer n — the number of card types.

The second line contains n space-separated integers a[1], a[2], …, a[n] indicating the number of cards drawn of each type.

outputFormat

Print a single integer — the number of winning combinations modulo 998244353.

sample

1
3

1