25613번 - 수 만들기

세빈이에게는 0이 아닌 숫자가 여러 개 있다.

세빈이는 이 숫자들을 이어 붙이지 않고, 일렬로 모두 나열한 뒤 숫자 사이사이에 나눗셈 기호를 하나씩 적었다. 그런 다음, 괄호를 원하는 만큼 쳐서 올바른 수식을 만든 뒤 계산해서 수를 만들려고 한다.

세빈이가 1, 2, 3, 4, 6을 가지고 있다고 해 보자. 세빈이는 다음과 같은 수들을 만들 수 있다.

(6 ÷ (4 ÷ 1) ÷ 3) ÷ 2 = 14(6 ÷ 3) ÷ (4 ÷ 1) ÷ 2 = 14(2 ÷ (3 ÷ 4)) ÷ (6 ÷ 1) = 49(4 ÷ 6 ÷ (1 ÷ 2)) ÷ 3 = 494 ÷ (2 ÷ 1 ÷ (6 ÷ 3)) = 4

이런 식으로 만들 수 있는 수는 1144, 136, 116, 19, 14, 49, 1, 94, 4, 9, 16, 36, 144의 13가지이다.

세빈이는 숫자 i가 A_i개 있을 때 만들 수 있는 수의 개수를 구하려고 한다. 그러나 숫자가 너무 많아지자, 나열하는 방법의 수도 너무 많아졌고, 괄호를 치는 방법도 너무 많아져서 세빈이는 만들 수 있는 수의 개수를 구하는 데 어려움을 겪고 있다. 세빈이를 도와 만들 수 있는 수의 개수를 구하자.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. (1 ≤ T ≤ 10⁵)

각 테스트 케이스마다 한 줄에 9개의 정수 A_i가 공백으로 구분되어 주어진다. (0 ≤ A_i ≤ 10⁹, 1 ≤ ∑ A_i)

각 테스트 케이스마다 한 줄에 만들 수 있는 수의 개수를 998 244 353으로 나눈 나머지를 출력한다.