"""
This program outputs a matrix whose determinant is the number
of domino tilings of the input region.  The matrix should be fed
to Sagemath. This input format allows for computing the number of
matchings of any bipartite planar graph.

The region should be given as a pattern of V's, A's, <'s, >'s, and X's.
All characters after a percent are ignored.  Currently, the input must
fit in a rectangle with 500 rows and 200 columns.

The five main symbols and their meanings are as follows:

- X: A cell occupied by an X can be covered by a domino in any of the
  four cardinal  directions (rightward, leftward, upward, downward).
- V: A cell occupied by a  V can be covered by a domino any way but DOWN.
- A: A cell occupied by an A can be covered by a domino any way but UP.
- <: A cell occupied by a  < can be covered by a domino any way but LEFT.
- >: A cell occupied by a  > can be covered by a domino any way but RIGHT.

Note: A good mnemonic for these conventions comes from the fact that
if one has a region tiled by equilateral triangles
                                    ____
                                   /\  /\
                                  /__\/__\
                                  \  /\  /
                                   \/__\/

and one wishes to pair up the triangles to form a rhombus-tiling, the
triangles that look like V's are the ones that can pair (sort of) leftward,
(sort of) rightward, or upward.  Etc.

There can be holes in the array of non-blank characters, and these
holes can be arbitrary.  For instance, the graphs

o--o--o
|     |
o     o
|     |
o--o--o

and

o--o--o--o
|        |
o--o--o--o

are both acceptable; the former can be represented as

XXX
X X
XXX

while the latter can be represented as

AVVA
VAAV

How to call the program from sagemath:
======================================

%attach vax_sage.py
vax_string = "AVVA\nVAAV"
matchings(vax_string)

AUTHORS:

Greg Kuperberg, Jim Propp, and David Wilson

Frédéric Chapoton for the translation to sagemath.
"""
MAX_LENGTH = 202
MAX_WIDTH = 502


def matchings(vax):
    """
    Compute the number of matchings of a bipartite planar graph.

    The input is given in the vax format.

    EXAMPLES::

        sage: matchings("XXX\nX")
        1
        sage: matchings("AVVA\nVAAV")
        2
        sage: matchings("XXX\nX X\nXXX")
        2
        sage: matchings("XX\nXX")
        2
        sage: matchings("XXX\nXXX")
        3
        sage: matchings("XXXX\nXXXX")
        5
        sage: matchings("XXXXX\nXXXXX")
        8
        sage: matchings(" XX \nXXXX\nXXXX\n XX ")
        8
        sage: matchings("  XX\n XXXX\nXXXXXX\nXXXXXX\n XXXX\n  XX")
        64
    """
    FREE = -1

    # load the image
    data = vax.splitlines()
    data = [u.rstrip() for u in data if u.strip()]
    width = max(len(u) for u in data) + 2
    length = len(data) + 2
    assert width < MAX_WIDTH
    assert length < MAX_LENGTH
    pict = [[''] * width for _ in range(length)]
    p = [[0] * width for _ in range(length)]
    gap_table = [[0] * width for _ in range(length)]
    for i in range(length - 2):
        for j in range(width - 2):
            if i < len(data) and j < len(data[i]):
                pict[i + 1][j + 1] = data[i][j]

    # cleanup
    for i in range(length):
        flag = False
        for j in range(width):
            if pict[i][j] == '%':
                flag = True
            if flag or pict[i][j] not in ['X', 'A', 'V', '<', '>']:
                pict[i][j] = ''

    # preparation
    rows = columns = 0
    for i in range(length):
        gaps = 1
        for j in range(width):
            if pict[i][j] == '':
                gaps *= -1
            gap_table[i][j] = gaps
            if (i + j) % 2:
                if pict[i][j] == '':
                    p[i][j] = FREE
                else:
                    p[i][j] = columns
                    columns += 1
            else:
                if pict[i][j] == '':
                    p[i][j] = FREE
                else:
                    p[i][j] = rows
                    rows += 1

    assert rows == columns

    # matrix computation
    matrix_data = []
    for i in range(1, length - 1):
        for j in range(i % 2, width - 1, 2):
            if p[i][j] != FREE:
                one_column = []
                for k in range(columns):
                    entry = 0
                    if (k == p[i + 1][j] and pict[i][j] != 'V' and
                            pict[i + 1][j] != 'A'):
                        entry = gap_table[i][j]
                    if (k == p[i - 1][j] and pict[i][j] != 'A' and
                            pict[i - 1][j] != 'V'):
                        entry = gap_table[i-1][j]
                    if (k == p[i][j + 1] and pict[i][j] != '>' and
                            pict[i][j + 1] != '<'):
                        entry = 1
                    if (k == p[i][j - 1] and pict[i][j] != '<' and
                            pict[i][j - 1] != '>'):
                        entry = -1
                    one_column.append(entry)
                matrix_data.append(one_column)

    return abs(matrix(ZZ, rows, columns, matrix_data).det())