output_description: Print how many sequences satisfy the conditions, modulo 10^9+7.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      n
attempt: import numpy as np
  
  n = int(input())
  
  if n == 1:
      print(1)
  else:
      res_v = np.zeros(n + 1, dtype="int64")
      res_v_cumsum = np.zeros(n + 1, dtype="int64")
      res_v[0] = 0
      res_v[1] = 1
      res_v[2] = 1
      res_v_cumsum[0] = 0
      res_v_cumsum[1] = 1
      res_v_cumsum[2] = 2
  
      M = 1000000007
  
      for k in range(3, n):
          res_v[k] = (1 + res_v_cumsum[k - 1] - res_v[k - 2]) % M
          res_v_cumsum[k] = (res_v_cumsum[k - 1] + res_v[k]) % M
  
      print(
          (
              ((res_v_cumsum[n - 2] * (((n - 1) * (n - 1)) % M)) % M)
              + ((res_v_cumsum[n - 1] * (n - 1)) % M)
              + n
              + (n - 1) * (n - 1) % M
          )
          % M
      )
  
problem_description: Statement
  
  How many infinite sequences a_1, a_2, ... consisting of {{1, ... ,n}} satisfy
  the following conditions?
  
    * The n-th and subsequent elements are all equal. That is, if n \leq i,j, a_i = a_j.
    * For every integer i, the a_i elements immediately following the i-th element are all equal. That is, if i < j < k\leq i+a_i, a_j = a_k.
  
  Find the count modulo 10^9+7.
samples: [{"input": "2", "output": "4\n    \n\nThe four sequences that satisfy the conditions are:\n\n  * 1, 1, 1, ...\n  * 1, 2, 2, ...\n  * 2, 1, 1, ...\n  * 2, 2, 2, ...\n\n* * *"}, {"input": "654321", "output": "968545283"}]