@chen_zhe

题目描述

给定一个长度为 $N$ 的序列，求出该序列中每个可能区间 $(i,j)$ 中的最小值并相加，其中 $0\leq i\leq j\leq 10^4$，结果对 $10^9+7$ 取模。序列首项为第 $0$ 项。

输入格式

每个数据共有不超过 $120$ 组的多组数据。

对于每组数据，第一行输入 $N$ ，第二行输入一个表示该序列的字符串，字符串第 $i$ 位（从第 $0$ 位开始）表示序列的第 $i$ 项。

输出格式

对于每组数据，每行输出一个如题所述的答案 $R$。

提示/说明

【样例解释】

对于第 $1$ 组数据，所有可能的区间和结果分别为：

$(0,0)\Rightarrow 1, (0,1)\Rightarrow 1, (0,2)\Rightarrow 1, (1,1)\Rightarrow 4, (1,2)\Rightarrow 3, (2,2)\Rightarrow 3$。

所以 $R=1+1+1+4+3+3=13$。

对于第 $2$ 组数据，所有可能的区间和结果为：

$(0,0)\Rightarrow 4, (0,1)\Rightarrow 1, (0,2)\Rightarrow 1, (1,1)\Rightarrow 1, (1,2)\Rightarrow 1, (2,2)\Rightarrow 3$。

所以 $R=11$。

对于第 $3$ 组数据，所有可能的区间和结果为：

$(0,0)\Rightarrow 1, (0,1)\Rightarrow 1, (0,2)\Rightarrow 1, (1,1)\Rightarrow 2, (1,2)\Rightarrow 1, (2,2)\Rightarrow 1$。

所以 $R=7$。

【数据范围】

对于 $100\%$ 的数据， $1\leq N\leq 10^4$。

### 题目描述

给定一个长度为 $N$ 的序列，求出该序列中每个区间 $(i,j)$ 中的最小值并相加，其中 $0\leq i\leq j\leq 10^4$，结果对 $10^9+7$ 取模。序列首项为第 $0$ 项。

### 输入格式

每个数据共有不超过 $120$ 组的多组数据。

对于每组数据，第一行输入 $N$ ，第二行输入一个表示该序列的字符串，字符串第 $i$ 位（从第 $0$ 位开始）表示序列的第 $i$ 项。

### 输出格式

对于每组数据，每行输出一个如题所述的答案 $R$。

### 提示/说明

【样例解释】

对于第 $1$ 组数据，所有可能的区间和结果分别为：

$(0,0)\Rightarrow 1, (0,1)\Rightarrow 1, (0,2)\Rightarrow 1, (1,1)\Rightarrow 4, (1,2)\Rightarrow 3, (2,2)\Rightarrow 3$。

所以 $R=1+1+1+4+3+3=13$。

对于第 $2$ 组数据，所有可能的区间和结果为：

$(0,0)\Rightarrow 4, (0,1)\Rightarrow 1, (0,2)\Rightarrow 1, (1,1)\Rightarrow 1, (1,2)\Rightarrow 1, (2,2)\Rightarrow 3$。

所以 $R=11$。

对于第 $3$ 组数据，所有可能的区间和结果为：

$(0,0)\Rightarrow 1, (0,1)\Rightarrow 1, (0,2)\Rightarrow 1, (1,1)\Rightarrow 2, (1,2)\Rightarrow 1, (2,2)\Rightarrow 1$。

所以 $R=7$。

【数据范围】

对于 $100\%$ 的数据， $1\leq N\leq 10^4$。