Description

You are transformed into a toad

As a toad, you can jump 1-3 block(s)

Starting from the 1^st block, how many way you can reach until the N^th block?

Also, there might be a hole in the block, as toad can't jump into that block

Hint: You might want to use long long to store

 

Sample IO #1 testcase explanation
[0, 0, 0, 0, 0]
There are 7 ways:

• 1 jump, 1 jump, 1 jump, 1 jump
• 2 jump, 1 jump, 1 jump
• 1 jump, 2 jump, 1 jump,
• 1 jump, 1 jump, 2 jump
• 2 jump, 2 jump
• 3 jump, 1 jump
• 1 jump, 3 jump

Sample IO #3 testcase explanation

[0, 1, 1, 0, 0]

There is only 1 way to solve this:

• 3 jump, 1 jump

Input

There are T testcases

first line of each testcase has integer N

second line of each testcase has N elements, either 0 or 1

0 means default block, 1 means hole

1 <= T <= 100

2 <= N <= 50

The first and last block can't be a hole

Output

The integer consist how many possible ways to do it, with a newline character

Sample Input  Download

Sample Output  Download

Tags

Discuss