





from __future__ import annotations

from collections import namedtuple
from dataclasses import dataclass



@dataclass
class 					A__   :
      _UpperCAmelCase	:int
      _UpperCAmelCase	:TreeNode | None						    =   None
      _UpperCAmelCase	:TreeNode | None						    =   None


__lowerCamelCase       :     Tuple   =     namedtuple("""CoinsDistribResult""", """moves excess""")



def 		A_				(     _lowerCAmelCase     )						-> int:

 if root is None:
  return 0

 # Validation
 def count_nodes(_lowerCAmelCase     ) -> int:
  if node is None:
   return 0

  return count_nodes(node.left     ) + count_nodes(node.right     ) + 1

 def count_coins(_lowerCAmelCase     ) -> int:
  if node is None:
   return 0

  return count_coins(node.left     ) + count_coins(node.right     ) + node.data

 if count_nodes(_lowerCAmelCase     ) != count_coins(_lowerCAmelCase     ):
  raise ValueError("The nodes number should be same as the number of coins"     )

 # Main calculation
 def get_distrib(_lowerCAmelCase     ) -> CoinsDistribResult:

  if node is None:
   return CoinsDistribResult(0							,   1     )

  UpperCamelCase	,    UpperCamelCase	:					Tuple       	=   get_distrib(node.left     )
  UpperCamelCase	,    UpperCamelCase	:					Optional[Any]       	=   get_distrib(node.right     )

  UpperCamelCase	:					str       	=   1 - left_distrib_excess
  UpperCamelCase	:					Optional[Any]       	=   1 - right_distrib_excess

  UpperCamelCase	:					str       	=   (
      left_distrib_moves
      + right_distrib_moves
      + abs(_lowerCAmelCase     )
      + abs(_lowerCAmelCase     )
  )
  UpperCamelCase	:					str       	=   node.data - coins_to_left - coins_to_right

  return CoinsDistribResult(_lowerCAmelCase							,   _lowerCAmelCase     )

 return get_distrib(_lowerCAmelCase     )[0]


if __name__ == "__main__":
    import doctest

    doctest.testmod()







def 		A_				(     _lowerCAmelCase = 50     )						-> int:
 UpperCamelCase	:					List[Any]       	=   [[0] * 3 for _ in range(length + 1     )]

 for row_length in range(length + 1     ):
  for tile_length in range(2							,   5     ):
   for tile_start in range(row_length - tile_length + 1     ):
    different_colour_ways_number[row_length][tile_length - 2] += (
        different_colour_ways_number[row_length - tile_start - tile_length][
            tile_length - 2
        ]
        + 1
    )

 return sum(different_colour_ways_number[length]     )


if __name__ == "__main__":
    print(f"""{solution() = }""")
