Verify a ballot triangle A ballot number, which we'll label B, is the number of ways of arranging the numbers from 1 through B(B+1)/2 into a triangle, such that each row and column is in any increasing order. The first four ballot numbers are:

a(0) = 1
a(1) = 1
a(2) = 1
a(3) = 2


a(3) is 2, which means that there are 2 ways of arranging the numbers from 1 to 3(3+1)/2 = 6 in such a triangle:

1          1
2 3    or  2 4
4 5 6      3 5 6


See the OEIS sequence entry for more details.

Your challenge, given a ballot triangle, is to verify its correctness. If it satisfies the conditions of a ballot triangle (rows and columns increasing), you should output how many other ways (excluding the one in the input) there are to arrange the triangle correctly. If the input triangle is incorrectly constructed, you should output nothing.

Trailing newlines are allowed.

Input

A triangle of numbers, which may or may not be a valid ballot triangle. For example:

1
2 3
4 5 6

1
10 5 
9 8 2
7 6 4 3

1
3 2

9
2 11
14 3 5
12 8 1 7
15 13 10 4 6

1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
16 17 18 19 20 21


Output

If the input is a valid ballot triangle, the remaining number of ways to arrange the same numbers in a valid ballot triangle. If the input is not a valid ballot triangle, nothing. For example, the inputs above produce these outputs (&lt;nothing&gt; is a placeholder for an actual empty output):

1                     # the same as a(3)-1

&lt;nothing&gt;

&lt;nothing&gt;

&lt;nothing&gt;

33591                 # the same as a(6)-1


Scoring

This is code-golf: as usual, lowest byte-count wins. Tiebreaker is earliest posted.
Jelly, 20 bytes

;Zµ⁼Ṣ€
ẋÇFŒ!ṁ€⁸ÇÐfL’


For valid ballot triangles, run time and memory usage are at least O(n!), where n is the number of entries of the triangle. Invalid ones are recognized by crashing, thus printing nothing.

Try it online!

Test run

Locally, I was able to verify that a(4) is calculated correctly.

$ time jelly eun ';Zµ⁼Ṣ€¶ẋÇFŒ!ṁ€⁸ÇÐfL’' '[1],[2,3],[4,5,6],[7,8,9,10]'
11

real    6m9.829s
user    6m7.930s
sys     0m2.579s


How it works

;Zµ⁼Ṣ€         Helper link. Argument: T (triangular array)

 Z             Zip/transpose T.
;              Concatenate the original and the transposed copy.
  µ            Begin a new monadic chain, with the previous result (R) as argument.
    Ṣ€         Sort each array in R.
   ⁼           Test for equality with R.
               This returns 1 if T is a ballot triangle, 0 if not.

ẋÇFŒ!ṁ€⁸ÇÐfL’  Main link. Argument: A (triangular array)

 Ç             Call the helper link with argument A.
ẋ              Repeat A that many times.
               This yields an empty array if A is not a ballot triangle.
  F            Flatten the result.
   Œ!          Generate all permutations of the digits of A.
     ṁ€⁸       Mold each permutation like A, i.e., give it triangular form.
               This crashes if permutation array is empty.
        ÇÐf    Filter; keep permutations for which the helper link returns 1.
           L’  Compute the length and decrement it.