TouchStone
  Please Login
ログイン 登録
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P7873
  • 問題
  • P7873aba
    制限 : 時間制限 : - MS   メモリ制限 : - KB
    審判説明 : 1s,65536
    問題説明

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

    入力形式

    第一行一个整数n,表示序列a的长度。
    第二行包括n个整数,表示a1,a2,a3,...,an-1,an。

    出力形式

    一行,一个整数表示Σ(1<=l<=r<=n)aba(l,r)的值对1000000007取模后的结果。

    サンプル入力 1

    3
    1 2 3

    サンプル出力 1

    22

    样例1解释:
    aba(1,1)=2(空序列,{a1})
    aba(2,2)=2,aba(3,3)=2,aba(1,2)=4,aba(2,3)=4,aba(1,3)=8
    共2+2+2+4+4+8=22

    サンプル入力 2

    8
    8 4 1 2 5 6 2 1

    サンプル出力 2

    952

    ヒント

    对于100%的数据,1<=n<=100000,|ai|<=1e9。