Напомним, что граф - это совокупность вершин и ребер, соединяющих эти вершины, и что две вершины, соединенные ребром, называются соседними.
Графы могут быть представлены в Евклидовом пространстве путем назначения каждой вершине точки Евклидового пространства.
Гибкий граф - это представление графа, в котором возможно непрерывно перемещать одну или более вершин таким образом, что расстояние между как минимум двумя несоседними вершинами изменяется, в то время как расстояния между всеми парами соседних вершин остаются неизменными.
Жесткий граф - это представление графа, которое не является гибким.
Иными словами, граф является жестким, если при замене его вершин на свободно вращающиеся шарниры, а его ребер - на стержни, никакая часть графа не сможет двигаться независимо от остальных частей.

Графы-сетки, представленные на Евклидовой плоскости, не являются жесткими, как показывает следующая анимация:

Однако, их возможно сделать жесткими, добавив диагональные ребра в ячейках. Например, для графа-сетки 2 × 3 существует 19 способов превратить его в жесткий граф:

Заметим, что в рамках этой задачи мы не рассматриваем изменение направления диагонального ребра или добавление двух диагональных ребер в ячейку как различные способы превращения в жесткий граф.

Пусть R(m,n) будет количеством способов первращения графа-сетки m × n в жесткий граф.
Например, R(2,3) = 19 и R(5,5) = 23679901.

Определим S(N) как ∑R(i,j) для 1 ≤ i, j ≤ N.
Например, S(5) = 25021721.
Найдите S(100), в качестве ответа приведите остаток от деления полученного числа на 1000000033.