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 sys
  
  readline = sys.stdin.readline
  MOD = 10**9 + 7
  N = int(readline())
  
  dp1 = [0] * (N + 1)
  Dp1 = [0] * (N + 1)
  dp2 = [0] * (N + 1)
  Dp2 = [0] * (N + 1)
  dp1[0] = 1
  Dp1[0] = 1
  dp2[0] = N - 1
  Dp2[0] = N - 1
  dp1[1] = N - 1
  dp2[1] = (N - 1) ** 2
  dp1[2] = N - 1
  dp2[2] = (N - 1) ** 2
  Dp1[1] = Dp1[0] + dp1[1]
  Dp2[1] = Dp2[0] + dp2[1]
  Dp1[2] = Dp1[1] + dp1[2]
  Dp2[2] = Dp2[1] + dp2[2]
  for i in range(3, N + 1):
      dp1[i] = (dp1[i - 1] + Dp1[i - 3] - 1) % MOD
      dp2[i] = (dp2[i - 1] + Dp2[i - 3]) % MOD
      Dp1[i] = (Dp1[i - 1] + dp1[i]) % MOD
      Dp2[i] = (Dp2[i - 1] + dp2[i]) % MOD
  print((Dp1[N - 1] + Dp2[N - 1]) % 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"}]