You've got an array, consisting of n integers: a 1 , a 2 , ..., a n . Your task is to quickly run the queries of two types: Assign value x to all elements from l to r inclusive. After such query the values of the elements of array a l , a l + 1 , ..., a r become equal to x . Calculate and print sum , where k doesn't exceed 5 . As the value of the sum can be rather large, you should print it modulo 1000000007 (10 9 + 7) . The first line contains two integers n and m ( 1 ≤ n , m ≤ 10 5 ), showing, how many numbers are in the array and the number of queries, correspondingly. The second line contains n integers: a 1 , a 2 , ..., a n ( 0 ≤ a i ≤ 10 9 ) — the initial values of the array elements. Then m queries follow, one per line: The assign query has the following format: " ", ( 1 ≤ l ≤ r ≤ n ; 0 ≤ x ≤ 10 9 ). The query to calculate the sum has the following format: " ", ( 1 ≤ l ≤ r ≤ n ; 0 ≤ k ≤ 5 ). All numbers in the input are integers. For each query to calculate the sum print an integer — the required sum modulo 1000000007 (10 9 + 7) .