CF1621G Weighted Increasing Subsequences

You are given the sequence of integers $ a_1, a_2, \ldots, a_n $ of length $ n $ . The sequence of indices $ i_1 < i_2 < \ldots < i_k $ of length $ k $ denotes the subsequence $ a_{i_1}, a_{i_2}, \ldots, a_{i_k} $ of length $ k $ of sequence $ a $ . The subsequence $ a_{i_1}, a_{i_2}, \ldots, a_{i_k} $ of length $ k $ of sequence $ a $ is called increasing subsequence if $ a_{i_j} < a_{i_{j+1}} $ for each $ 1 \leq j < k $ . The weight of the increasing subsequence $ a_{i_1}, a_{i_2}, \ldots, a_{i_k} $ of length $ k $ of sequence $ a $ is the number of $ 1 \leq j \leq k $ , such that exists index $ i_k < x \leq n $ and $ a_x > a_{i_j} $ . For example, if $ a = [6, 4, 8, 6, 5] $ , then the sequence of indices $ i = [2, 4] $ denotes increasing subsequence $ [4, 6] $ of sequence $ a $ . The weight of this increasing subsequence is $ 1 $ , because for $ j = 1 $ exists $ x = 5 $ and $ a_5 = 5 > a_{i_1} = 4 $ , but for $ j = 2 $ such $ x $ doesn't exist. Find the sum of weights of all increasing subsequences of $ a $ modulo $ 10^9+7 $ .

N/A

N/A

In the first test case the following increasing subsequences of $ a $ have not zero weight: - The weight of $ [a_1] = [6] $ is $ 1 $ . - The weight of $ [a_2] = [4] $ is $ 1 $ . - The weight of $ [a_2, a_3] = [4, 8] $ is $ 1 $ . - The weight of $ [a_2, a_4] = [4, 6] $ is $ 1 $ . The sum of weights of increasing subsequences is $ 4 $ .In the second test case there are $ 7 $ increasing subsequences of $ a $ with not zero weight: $ 3 $ with weight $ 1 $ , $ 3 $ with weight $ 2 $ and $ 1 $ with weight $ 3 $ . The sum of weights is $ 12 $ .