对于任意一个序列a={a1a2a3...an-1an},定义其aba(lr)为a[l]~a[r]中不同的子序列个数(包含a[l]与a[r]).特别地,空序列也被称为一个子序列.
出题人很无聊很菜,只会阿巴阿巴,于是定义了一个函数aba(lr)={alal+1al+2...ar-1ar}中不同的子序列的个数.
出题者太菜了,为了让题目简单点,这里的子序列是普通子序列,不一定要求连续.~~(出题人老好人了)~~长度为n的序列a与长度为m的序列b被称为不同的,当且仅当n!=m,或存在i使得ai!=bi.
若不满足任一上述两个条件则称两个序列是相同的.现在要求对于一个长度为n的序列a,Σ(1<=l<=r<=n)aba(lr)的值是多少.
由于结果可能很大,请输出它对1000000007取模的结果.
第一行一个整数n,表示序列a的长度.
一行,一个整数表示Σ(1<=l<=r<=n)aba(lr)的值对1000000007取模后的结果.
样例1解释:
共2+2+2+4+4+8=22