CF788E New task

On the 228-th international Uzhlyandian Wars strategic game tournament teams from each country are called. The teams should consist of $ 5 $ participants. The team of Uzhlyandia will consist of soldiers, because there are no gamers. Masha is a new minister of defense and gaming. The prime duty of the minister is to calculate the efficiency of the Uzhlandian army. The army consists of $ n $ soldiers standing in a row, enumerated from $ 1 $ to $ n $ . For each soldier we know his skill in Uzhlyandian Wars: the $ i $ -th soldier's skill is $ a_{i} $ . It was decided that the team will consist of three players and two assistants. The skills of players should be same, and the assistants' skills should not be greater than the players' skill. Moreover, it is important for Masha that one of the assistants should stand in the row to the left of the players, and the other one should stand in the row to the right of the players. Formally, a team is five soldiers with indexes $ i $ , $ j $ , $ k $ , $ l $ , $ p $ , such that $ 1

The first line contains single integer $ n $ ( $ 1

Print $ m $ integers — the number of distinct teams after each change. Print the answers modulo $ 1000000007 $ ( $ 10^{9}+7 $ ).

In the first example, after the first change the only team consists of soldiers $ [1,2,4,5,6] $ . After the second change any five soldiers can form a team. In the first example after the first change the only team is soldiers $ [1,2,3,7,8] $ . After the second change the possible teams are: $ [1,2,3,5,7] $ , $ [1,2,3,5,8] $ , $ [1,2,3,7,8] $ , $ [1,2,5,7,8] $ , $ [1,3,5,7,8] $ , $ [2,3,5,7,8] $ . After the third change the possible teams are: $ [1,3,5,7,8] $ , $ [2,3,5,7,8] $ .