"""simple docstring"""



from __future__ import annotations

import time

__lowercase		:		Optional[int]														=							list[tuple[int, int]]

__lowercase		:		Tuple														=							[
    [0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0],
    [1, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0],
]

__lowercase		:		Dict														=							[[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right



class      _A	:




    """simple docstring"""




    def __init__(		self							:     Any	,      A_							:     int	,      A_							:     int	,      A_							:     int	,      A_							:     int	,      A_							:     Node | None    )    ->       Any:
         __snake_case				=							pos_x
         __snake_case				=							pos_y
         __snake_case				=							(pos_y, pos_x)
         __snake_case				=							goal_x
         __snake_case				=							goal_y
         __snake_case				=							parent






class      _A	:




    """simple docstring"""




    def __init__(		self							:     str	,      A_							:     tuple[int, int]	,      A_							:     tuple[int, int]    )    ->       List[str]:
         __snake_case				=							Node(start[1]	,      start[0]	,      goal[1]	,      goal[0]	,      A_    )
         __snake_case				=							Node(goal[1]	,      goal[0]	,      goal[1]	,      goal[0]	,      A_    )

         __snake_case				=							[self.start]
         __snake_case				=							False
    def  lowercase					(		self							:     Union[str, Any]    )    ->       Path | None:
         while self.node_queue:
              __snake_case				=							self.node_queue.pop(0    )

              if current_node.pos == self.target.pos:
                   __snake_case				=							True
                   return self.retrace_path(A_    )

              __snake_case				=							self.get_successors(A_    )

              for node in successors:
                   self.node_queue.append(A_    )

         if not self.reached:
              return [self.start.pos]
         return None
    def  lowercase					(		self							:     List[Any]	,      A_							:     Node    )    ->       list[Node]:
         __snake_case				=							[]
         for action in delta:
              __snake_case				=							parent.pos_x + action[1]
              __snake_case				=							parent.pos_y + action[0]
              if not (0 <= pos_x <= len(grid[0]    ) - 1 and 0 <= pos_y <= len(A_    ) - 1):
                   continue

              if grid[pos_y][pos_x] != 0:
                   continue

              successors.append(
                  Node(A_	,      A_	,      self.target.pos_y	,      self.target.pos_x	,      A_    )    )
         return successors







    def  lowercase					(		self							:     Dict	,      A_							:     Node | None    )    ->       Path:
         __snake_case				=							node
         __snake_case				=							[]
         while current_node is not None:
              path.append((current_node.pos_y, current_node.pos_x)    )
              __snake_case				=							current_node.parent
         path.reverse()
         return path






class      _A	:




    """simple docstring"""




    def __init__(		self							:     List[str]	,      A_							:     List[str]	,      A_							:     List[Any]    )    ->       int:
         __snake_case				=							BreadthFirstSearch(A_	,      A_    )
         __snake_case				=							BreadthFirstSearch(A_	,      A_    )
         __snake_case				=							False
    def  lowercase					(		self							:     List[str]    )    ->       Path | None:
         while self.fwd_bfs.node_queue or self.bwd_bfs.node_queue:
              __snake_case				=							self.fwd_bfs.node_queue.pop(0    )
              __snake_case				=							self.bwd_bfs.node_queue.pop(0    )

              if current_bwd_node.pos == current_fwd_node.pos:
                   __snake_case				=							True
                   return self.retrace_bidirectional_path(
                       A_	,      A_    )

              __snake_case				=							current_bwd_node
              __snake_case				=							current_fwd_node

              __snake_case				=							{
                  self.fwd_bfs: self.fwd_bfs.get_successors(A_    ),
                  self.bwd_bfs: self.bwd_bfs.get_successors(A_    ),
              }

              for bfs in [self.fwd_bfs, self.bwd_bfs]:
                   for node in successors[bfs]:
                        bfs.node_queue.append(A_    )

         if not self.reached:
              return [self.fwd_bfs.start.pos]
         return None







    def  lowercase					(		self							:     int	,      A_							:     Node	,      A_							:     Node    )    ->       Path:
         __snake_case				=							self.fwd_bfs.retrace_path(A_    )
         __snake_case				=							self.bwd_bfs.retrace_path(A_    )
         bwd_path.pop()
         bwd_path.reverse()
         __snake_case				=							fwd_path + bwd_path
         return path


if __name__ == "__main__":
       # all coordinates are given in format [y,x]
       import doctest

       doctest.testmod()
       __lowercase		:		Tuple														=							(0, 0)
       __lowercase		:		Optional[Any]														=							(len(grid) - 1, len(grid[0]) - 1)
       for elem in grid:
              print(elem)

       __lowercase		:		Optional[int]														=							time.time()
       __lowercase		:		List[Any]														=							BreadthFirstSearch(init, goal)
       __lowercase		:		Dict														=							bfs.search()
       __lowercase		:		str														=							time.time() - start_bfs_time

       print("Unidirectional BFS computation time : ", bfs_time)

       __lowercase		:		Any														=							time.time()
       __lowercase		:		List[str]														=							BidirectionalBreadthFirstSearch(init, goal)
       __lowercase		:		int														=							bd_bfs.search()
       __lowercase		:		Any														=							time.time() - start_bd_bfs_time

       print("Bidirectional BFS computation time : ", bd_bfs_time)
"""simple docstring"""



def    SCREAMING_SNAKE_CASE       (     snake_case):
     return 1 if digit in (0, 1) else (digit * factorial(digit - 1))





def    SCREAMING_SNAKE_CASE       (     snake_case):
     __snake_case				=							0
     __snake_case				=							number
     while duplicate > 0:
          __snake_case		,	__snake_case				=							divmod(snake_case,      10)
          fact_sum += factorial(snake_case)
     return fact_sum == number


if __name__ == "__main__":
       print("Program to check whether a number is a Krisnamurthy Number or not.")
       __lowercase		:		Optional[int]														=							int(input("Enter number: ").strip())
       print(
           F"""{number} is {'' if krishnamurthy(number) else 'not '}a Krishnamurthy Number."""
       )