text: '''The K factor of a string is defined as the number of
  times 'abba' appears as a substring.
  
  Given two numbers N and k, find the number of strings of
  length N with 'K factor' = k.
  
  The algorithms is as follows:
  
  dp[n][k] will be a 4 element array, wherein each element can be
  the number of strings of length n and 'K factor' = k which
  belong to the criteria represented by that index:
  
      dp[n][k][0] can be the number of strings of length n and K-factor = k
      which end with substring 'a'
      dp[n][k][1] can be the number of strings of length n and K-factor = k
      which end with substring 'ab'
      dp[n][k][2] can be the number of strings of length n and K-factor = k
      which end with substring 'abb'
      dp[n][k][3] can be the number of strings of length n and K-factor = k
      which end with anything other than the above substrings (anything other
      than 'a' 'ab' 'abb')
  
  Example inputs
  
  n=4 k=1  no of strings = 1
  n=7 k=1 no of strings = 70302
  n=10 k=2 no of strings = 74357
  
  '''
  
  
  def find_k_factor(n, k):
      dp = [[[0 for i in range(4)]for j in range((n-1)//3+2)]for k in range(n+1)]
      if(3*k+1 > n):
          return 0
      # base cases
      dp[1][0][0] = 1
      dp[1][0][1] = 0
      dp[1][0][2] = 0
      dp[1][0][3] = 25
  
      for i in range(2, n+1):
          for j in range((n-1)//3+2):
              if(j == 0):
                  # adding a at the end
                  dp[i][j][0] = dp[i-1][j][0] + dp[i-1][j][1] + dp[i-1][j][3]
  
                  # adding b at the end
                  dp[i][j][1] = dp[i-1][j][0]
                  dp[i][j][2] = dp[i-1][j][1]
  
                  # adding any other lowercase character
                  dp[i][j][3] = dp[i-1][j][0]*24+dp[i-1][j][1]*24+dp[i-1][j][2]*25+dp[i-1][j][3]*25
  
              elif(3*j+1 < i):
                  # adding a at the end
                  dp[i][j][0] = dp[i-1][j][0]+dp[i-1][j][1]+dp[i-1][j][3]+dp[i-1][j-1][2]
  
                  # adding b at the end
                  dp[i][j][1] = dp[i-1][j][0]
                  dp[i][j][2] = dp[i-1][j][1]
  
                  # adding any other lowercase character
                  dp[i][j][3] = dp[i-1][j][0]*24+dp[i-1][j][1]*24+dp[i-1][j][2]*25+dp[i-1][j][3]*25
  
              elif(3*j+1 == i):
                  dp[i][j][0] = 1
                  dp[i][j][1] = 0
                  dp[i][j][2] = 0
                  dp[i][j][3] = 0
  
              else:
                  dp[i][j][0] = 0
                  dp[i][j][1] = 0
                  dp[i][j][2] = 0
                  dp[i][j][3] = 0
  
      return sum(dp[n][k])
  