code is:-
include
using namespace std;
typedef long long int ll;
ll mod = 1000000007;
ll arr[10000010];
ll getMax(ll n)
{
ll mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}
void countSort(ll n,ll exp)
{
ll output[n+1];
ll i, cnt[10] = {0};
for (i = 0; i < n; i++)
cnt[ (arr[i]/exp)%10 ]++;
for (i = 1; i < 10; i++)
cnt[i] += cnt[i - 1];
for (i = n - 1; i >= 0; i--)
{
output[cnt[ (arr[i]/exp)%10 ] - 1] = arr[i];
cnt[ (arr[i]/exp)%10 ]--;
}
for (i = 0; i < n; i++)
arr[i] = output[i];
}
void radixsort(ll n)
{
ll m = getMax(n);
for (ll exp = 1; m/exp > 0; exp *= 10)
countSort(n, exp);
}
ll print(ll n)
{
ll sum=0;
for (ll i = 0; i < n; i++)
{
sum = (sum + (arr[i]*(i+1)))%mod;
}
return sum;
}
int main()
{
ll t,i,n,a,b;
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld%lld%lld",&n,&a,&b,&arr[0]);
for(i=1;i<n;i++)
{
arr[i] = (arr[i-1]*a+b)%mod;
}
radixsort(n);
printf("%lld\n",print(n));
}
return 0;
}
`