document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. using namespace std;
  2.  
  3. #include <iostream>
  4. #include <queue>
  5.  
  6. int main(void)
  7. {
  8.     int t;
  9.     cin >> t;
  10.    
  11.     for(int i=0; i<t; i++)
  12.     {
  13.         long long int a,b,c;
  14.         int n;
  15.         priority_queue <long long int, vector<long long int>, greater<long long int> > min;
  16.         priority_queue <long long int> max;
  17.         long long int sum = 1;
  18.         long long int median;
  19.         cin >> a >> b >> c >> n;
  20.        
  21.         if(n == 1)
  22.         {
  23.             cout << "1" << endl;
  24.             continue;
  25.         }
  26.        
  27.         max.push(1);
  28.        
  29.         for(int j = 2; j<=n; j++)
  30.         {
  31.             if(max.size() >= min.size())
  32.               median = max.top();
  33.             else
  34.               median = min.top();
  35.            
  36.             long long int x = (a * median + b * j + c) % 1000000007;
  37.            
  38.             while(x < 0)
  39.                 x += 1000000007;
  40.            
  41.             sum += x;
  42.                
  43.             if(x <= max.top())
  44.               max.push(x);
  45.             else
  46.               min.push(x);
  47.            
  48.             long long int min_size = min.size();
  49.             long long int max_size = max.size();
  50.    
  51.             if((min_size - max_size) > 1)
  52.             {
  53.                 max.push(min.top());
  54.                 min.pop();
  55.             }
  56.             else if((max_size - min_size) > 1)
  57.             {
  58.                 min.push(max.top());
  59.                 max.pop();
  60.             }
  61.         }
  62.         cout << sum << endl;
  63.     }
  64.    
  65.     return 0;
  66. }
');