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: #!/usr/bin/env python3
  # -*- coding: utf-8 -*-
  
  from random import *
  
  
  def readln():
      _res = list(map(int, str(input()).split(" ")))
      return _res
  
  
  p = 1000000000 + 7
  
  n = readln()[0]
  f = [0 for i in range(0, n + 1)]
  f[1] = n
  f[2] = n * n
  s = f[:]
  s[2] = f[1] + f[2]
  for i in range(3, n + 1):
      f[i] = f[i - 1] + (n - 1) * (n - 1)
      f[i] = f[i] + s[i - 3] + (n - i + 2)
      f[i] = f[i] % p
      s[i] = s[i - 1] + f[i]
      s[i] = s[i] % p
  print(f[n])
  
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"}]