output_description: Print the number of permutations that can be produced as P after the
  operation.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N K
      P_0 P_1 \cdots P_{N-1}
attempt: import sys
  
  input = sys.stdin.readline
  sys.setrecursionlimit(pow(10, 6))
  
  
  def dfs(digd, tmpk):
      if tmpk == k:
          ans = {}
          for i in range(n):
              tmp = 0
              for dig in v[i]:
                  if tmp + digd[int(dig)] > len(w[i]):
                      return False, {}
                  elif int(dig) not in ans:
                      ans[int(dig)] = w[i][tmp : tmp + digd[int(dig)]]
                      tmp += digd[int(dig)]
                  else:
                      if ans[int(dig)] != w[i][tmp : tmp + digd[int(dig)]]:
                          return False, {}
                      else:
                          tmp += digd[int(dig)]
              if tmp != len(w[i]):
                  return False, {}
          return True, ans
      else:
          for i in range(1, 4):
              digd[tmpk + 1] = i
              is_finished, ans = dfs(digd, tmpk + 1)
              if is_finished:
                  return True, ans
          return False, {}
  
  
  k, n = map(int, input().split())
  v, w = [], []
  for _ in range(n):
      _v, _w = input().strip().split()
      v.append(_v)
      w.append(_w)
  digd = {}
  _, ans = dfs(digd, 0)
  for i in range(1, k + 1):
      print(ans[i])
  
problem_description: Statement
  
  Snuke has a permutation (P_0,P_1,\cdots,P_{N-1}) of (0,1,\cdots,N-1).
  
  Now, he will perform the following operation **exactly once** :
  
    * Choose K consecutive elements in P and sort them in ascending order.
  
  Find the number of permutations that can be produced as P after the operation.
samples: [{"input": "5 3\n    0 2 1 4 3", "output": "2\n    \n\nTwo permutations can be produced as P after the operation: (0,1,2,4,3) and\n(0,2,1,3,4).\n\n* * *"}, {"input": "4 4\n    0 1 2 3", "output": "1\n    \n\n* * *"}, {"input": "10 4\n    2 0 1 3 7 5 4 6 8 9", "output": "6"}]