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: MOD = 10**9 + 7
  n = int(input())
  dp = [0 for _ in range(n + 1)]
  dp[0], dp[1], dp[2] = 1, 1, 1
  cum = [0 for _ in range(n + 1)]
  cum[0], cum[1], cum[2] = 1, 2, 3
  for i in range(3, n + 1):
      dp[i] = (dp[i - 1] + cum[i - 3]) % MOD
      cum[i] = (cum[i - 1] + dp[i]) % MOD
  ans = cum[n - 2] * (n - 1) * (n - 1) + dp[n - 1] * (n - 1) + cum[n - 2] * (n - 1) + 1
  print(ans % MOD)
  
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"}]