410570: GYM104053 D Digits

Richard loves range sums. Anita loves palindromes.

Richard has an array of $$$n$$$ non-negative integers $$$a_1,a_2,\dots,a_n$$$. He wants to split it into several segments and then calculate the range sums of each segment.

Anita wonders the number of partitions that the digits of the range sums form a palindrome. A string is a palindrome, if and only if it is the same as its reverse.

For example, array $$$a=[1,1,4,5,1,4,1,9,1,9]$$$ can be partitioned into $$$3$$$ segments $$$[1,1,4,5],[1,4,1,9,1],[9]$$$ and the sum of these segments are $$$11,16,9$$$, therefore this partition results in a string $$$11169$$$.

Note that the sum always doesn't contain prefix zeroes. That means the same partition will result in only one possible string.

Richard's array is too large, so Anita can't calculate the answer and cried. Can you help her?

Since the answer can be too large, you only need to answer it modulo $$$10^9+9$$$.

Each test contains multiple test cases.

The first line contains one single integer $$$t$$$ ($$$1 \leq t \leq 100$$$). The description of the $$$t$$$ test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 150$$$), the size of array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ ($$$0 \leq a_i \leq 666666$$$).

It is guaranteed that the sum of $$$n$$$ of all test cases doesn't exceed $$$200$$$.

For each test case, output an integer in one line, representing your answer modulo $$$10^9+9$$$.

5
2
123456 654321
5
0 0 0 0 0
6
1 1 1 1 1 1
7
1 1 4 5 1 4 1
9
1 2 3 1 1 1 2 1 1

2
16
8
4
6

In the first case, partition $$$[123456],[654321]$$$ results in $$$123456654321$$$, and partition $$$[123456,654321]$$$ results in $$$777777$$$, each of which is a palindrome.

In the second case, any partition will result in a string with only zeroes, obviously a palindrome. so the answer is $$$2^4 = 16$$$.

In the third case, valid partitions are

$$$[1],[1],[1],[1],[1],[1] \to 111111$$$,

$$$[1],[1],[1,1],[1],[1] \to 11211$$$,

$$$[1],[1,1],[1,1],[1] \to 1221$$$,

$$$[1],[1,1,1,1],[1] \to 141$$$,

$$$[1,1],[1],[1],[1,1] \to 2112$$$,

$$$[1,1],[1,1],[1,1] \to 222$$$,

$$$[1,1,1],[1,1,1] \to 33$$$,

$$$[1,1,1,1,1,1] \to 6$$$.