output_description: If E869120 can pay exactly N yen using only his 1-yen and 500-yen coins, print
  `Yes`; otherwise, print `No`.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      A
attempt: import sys
  from collections import deque
  
  sys.setrecursionlimit(10**9)
  
  H, W = map(int, input().split())
  
  Map = [[] for _ in range(H)]
  reached = [[-1] * W for _ in range(H)]
  route = [[False] * W for _ in range(H)]
  
  q = deque()
  check = False
  b = 0
  for y in range(H):
      for x in input():
          Map[y].append(x)
          if x == "#":
              b += 1
  
  
  def BFS(x, y, pre):
      global check
  
      if x >= W or y >= H or x < 0 or y < 0 or Map[y][x] == "#" or reached[y][x] >= 0:
          return
  
      reached[y][x] = pre + 1
  
      if x == (W - 1) and y == (H - 1):
          ans = H * W - reached[y][x] + 1 - b - 2
          print(ans)
          sys.exit()
  
      else:
          q.append((x + 1, y, pre + 1))
          q.append((x - 1, y, pre + 1))
          q.append((x, y + 1, pre + 1))
          q.append((x, y - 1, pre + 1))
  
  
  q.append((0, 0, -1))
  while q:
      BFS(*q.popleft())
  print(-1)
  
problem_description: Statement
  
  E869120 has A 1-yen coins and infinitely many 500-yen coins.  
  Determine if he can pay exactly N yen using only these coins.
samples: [{"input": "2018\n    218", "output": "Yes\n    \n\nWe can pay 2018 yen with four 500-yen coins and 18 1-yen coins, so the answer\nis `Yes`.\n\n* * *"}, {"input": "2763\n    0", "output": "No\n    \n\nWhen we have no 1-yen coins, we can only pay a multiple of 500 yen using only\n500-yen coins. Since 2763 is not a multiple of 500, we cannot pay this amount.\n\n* * *"}, {"input": "37\n    514", "output": "Yes"}]