https://codeiq.jp/magazine/2016/12/47476/

DivisionSum.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
#if DEBUG
		// sample
		Check(F(2),7);
		Check(F(3),600);
		Check(F(4),991111);
		Check(F(12),845575);
		
#endif		
		
		// Console.WriteLine(IsPrime(mod));	// true;
		
		int N = ri();
		Console.WriteLine(F(N));
		
	}
	
	static long mod = (long)1e6 + 3;
	
	static long F(int n){
		
		// n の約数の総和 DS(n) は 素因数分解 n = Π p_k ^ i_k (k = 1,2,...,m) がわかれば
		// 　DS(n) = (1 + p1 + p1^2 + … + p1^i_1) * (1 + p2 + p2^2 + … + p2^i_2) * … * (1 + p_m + p_m^2 + … + p_m^i_m)
		// と書けるので，(n!)^n を素因数分解することを考える
		//．
		// (n!)^n の素因数分解は n!の素因数分解の各指数をn倍すればいい．
		// n! の素因数分解は 1～nの素因数分解を地道に計算してもO(n^1,5)程度で n<1000程度なら問題ないが，
		// 素数べきの登場頻度を数えると O(n log n) 程度に落ちる．
		//
		// 幾何級数の部分の計算については，n<1000程度なら地道に計算しても間に合うが，
		// modが素数なので等比数列の和の公式を使ってO(log(mod))で求める
		
		int maxN = 1020000;
		bool[] isPrime = new bool[maxN];
		for(int i=2;i<maxN;i++) isPrime[i] = true;
		for(int i=2;i<maxN;i++){
			if(isPrime[i]){
				for(int j=i+i;j<maxN;j+=i) isPrime[j] = false;
			}
		}
		
		Dictionary<int,long> D = new Dictionary<int,long>();
		for(int p=2;p<=n;p++){
			if(!isPrime[p]) continue;
			D.Add(p,0);
			long k=p;
			while(k<=n){
				D[p] += (n/k);
				k *= p;
			}
			
			// n乗する
			D[p] *= n;
		}
		
		long ans = 1;
		foreach(var p in D.Keys){
			long sum = (PowMod(p,D[p]+1) - 1 + mod) % mod;
			long div = InvMod(p-1);
			sum *= div; sum %= mod;
			ans *= sum; ans %= mod;
		}
		
		return ans;
		
		
		
	}
	
	static bool IsPrime(long x){
		if(x == 1) return false;
		for(long i=2;i*i<=x;i++){
			if(x % i == 0) return false;
		}
		return true;
	}
	
	static long PowMod(long n,long k){
		
		if(k==0)return 1;
		if(n==0)return 0;
		long ret=1;
		long x=n;
		while(k>0){
			if((k&1)==1){ret*=x;ret%=mod;}
			
			x*=x;x%=mod;
			k>>=1;
		}
		return ret;
		
	}
	
	public static long InvMod(long n){
		//(mod-2)乗を返す
		// modが素数の時だけ!!!!
		return PowMod(n,mod-2);
	}
	
	static bool Check(long input, long ans){
		Console.Write(input==ans?"OK":"NG");
		if(input!=ans){
			Console.Write(": input={0},ans={1}",input,ans);
		}
		Console.WriteLine();
		return input==ans;
	}

	static int ri(){return int.Parse(Console.ReadLine());}}