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