COLLECT.cpp

	#include <iostream>
	#include <string>
	using namespace std;

	long ncr(int n,int r)  // This function will calculate the value of nCr
	{
		if((r==0)||(n==r))
			return 1;
		else 
			return (ncr(n-1,r-1)+ncr(n-1,r));
	}

	int main()
	{
		int n;
		cin>>n;
		int arr[n];
		for(int i=0;i<n;i++)
		{
			cin>>arr[i];
		}
		
		int q;
		cin>>q;
		while(q--)
		{
			string s;
			int left,right;
			cin>>s >>left >>right;

			if(s=="change")
			{
				arr[left-1]=right;
				continue;
			}
			
			int berries=0;

			for(int i=left-1;i<right;i++)
			{
				berries+=arr[i];
			}

			int len=(right-left+1); //length of interval
			int min_each=(berries/len); //Minimum no. og berries each will get
			int max_num=(berries%len); // No. of people will get (min_each+1) berries
			long res=ncr(len,max_num);  //variable res will store the total no. of possible way.


			/*
			My algorithm are like 
			1. Distribute the berries who will get (min_each+1).
			2. Keep going till total no. of recieptent become equal to max_num;
			3. Distribute the rest berries into rest people. They will get min_each ammount of berries.
			*/

			for(int i=0;i<max_num;i++)
				res*=ncr((berries-(i*(min_each+1))),(min_each+1));
		
			for(int i=0;i<(len-max_num-1);i++)
				res*=ncr((len-max_num-i)*min_each,min_each);	

			res%=3046201;
			cout<<res<<endl;
		}
		return 0;
	}