stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#define LL long long

#define PII pair<int,int>

using namespace std;

const int MAXN = 100005;



int N, MOD, dp[MAXN], up[MAXN];

vector<int> G[MAXN], pref[MAXN], suff[MAXN];



void dfs1(int v, int p) {

//	cout << "DFS1 " << v << " " << p << "\n";

	dp[v] = 1;

	for (int to : G[v]) {

		if (to == p) continue;

		dfs1(to, v);

		dp[v] = (LL)dp[v] * (dp[to] + 1) % MOD;

	}

	

	pref[v].resize(G[v].size() + 1);

	pref[v][0] = 1;

	for (int i = 0; i < G[v].size(); i++) {

		int to = G[v][i];

		LL mul = to == p ? 1 : dp[to] + 1;

		pref[v][i + 1] = pref[v][i] * mul % MOD;

	}

	

	suff[v].resize(G[v].size() + 1);

	suff[v][G[v].size()] = 1;

	for (int i = G[v].size() - 1; i >= 0; i--) {

		int to = G[v][i];

		LL mul = to == p ? 1 : dp[to] + 1;

		suff[v][i] = suff[v][i + 1] * mul % MOD;

	}

}



void dfs2(int v, int p) {

//	cout << "DFS2 " << v << " -> " << dp[v] << " " << up[v] << "\n";

	for (int i = 0; i < G[v].size(); i++) {

		int to = G[v][i];

		if (to == p) continue;

//		cout << "Set " << to << " " << i << " -> " << pref[v][i] << " " <<  suff[v][i + 1] << "\n";

		up[to] = (1LL + (LL)pref[v][i] * suff[v][i + 1] % MOD * up[v] % MOD) % MOD;

		dfs2(to, v);

	}

}



int main() {

	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> N >> MOD;

	for (int i = 0; i < N - 1; i++) {

		int x, y;

		cin >> x >> y;

		G[x].push_back(y);

		G[y].push_back(x);

	}

	

	dfs1(1, 1);

	up[1] = 1;

	dfs2(1, 1);

	

	for (int i = 1; i <= N; i++) {

		cout << (LL) dp[i] * up[i] % MOD << "\n";

	}

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

#define PII pair<int, int>

#define LL long long

using namespace std;

const int MAXN = 100005;

const LL INF = (LL)1e9 + 5;



int N, par[MAXN];

LL MOD, dp[MAXN], up_dp[MAXN];

vector<int> G[MAXN];



void dfs1(int v, int p) {

	par[v] = p;

	dp[v] = 1;

	for (int to : G[v]) {

		if (to != p) {

			dfs1(to, v);

			dp[v] = dp[v] * dp[to] % MOD;

		}

	}

	dp[v]++;

}



void dfs2(int v, int p) {

	LL suff;

	vector<LL> pref(G[v].size() + 1);

	pref[0] = suff = 1;

	for (int i = 0; i < G[v].size(); i++) {

		LL mul = (G[v][i] == p ? 1 : dp[G[v][i]]);

		pref[i + 1] = pref[i] * mul % MOD;

	}

	for (int i = G[v].size() - 1; i >= 0; i--) {

		if (G[v][i] != p) {

			up_dp[G[v][i]] = (suff * pref[i] % MOD * up_dp[v] + 1)% MOD;

			suff = suff * dp[G[v][i]] % MOD;

			dfs2(G[v][i], v);

		}

	}

}



int main() {

	ios_base::sync_with_stdio(0); cin.tie(0);



	cin >> N >> MOD;

	for (int i = 0; i < N - 1; i++) {

		int x, y;

		cin >> x >> y;

		G[x].push_back(y);

		G[y].push_back(x);

	}

	

	dfs1(1, 1);

	up_dp[1] = 1;

	dfs2(1, 1);

	

	for (int i = 1; i <= N; i++) {

		LL ans = up_dp[i];

		for (int to : G[i]) {

			if (to != par[i]) {

				ans = ans * dp[to] % MOD;

			}

		}

		cout << ans << "\n";

	}

	

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#define ull unsigned long long

#define ll long long

#define endl '\n'

#define pb push_back

#define mod 1000000007

#define mp make_pair

#define pi acos(-1)

#define line cout<<"----------------------------"<<endl

#define fast ios_base::sync_with_stdio(false); cin.tie(NULL)

#define filein freopen("input.txt","r",stdin)

#define fileout freopen("output.txt","w",stdout)

using namespace std;

const ll mx=200009;	

vector<int> v[mx]; 

ll ans[mx];

int n,m; 

ll upor[mx]; 

void dfs(int s, int par)

{

	ans[s]=1;

	for(auto x: v[s])

	{

		if(x==par) continue; 

		dfs(x,s);

		ans[s]*=ans[x]+1;

		ans[s]%=m;

	}

}

void dfs1(int s, int par)

{

	vector<ll> pre((int)v[s].size()+5),suf((int)v[s].size()+5);

	pre[0]=1; 

	for(int i=1;i<=(int)v[s].size();i++)

	{

		int x=v[s][i-1] ;

		pre[i] =pre[i-1];

		if(x==par) continue; 

		pre[i]*=(ans[x]+1); 

		pre[i]%=m; 

	}

	suf[(int)v[s].size()+1]=1; 

	for(int i=(int)v[s].size();i>0;i--)

	{

		suf[i]=suf[i+1] ; 

		int x=v[s][i-1] ; 

		if(x==par) continue; 

		suf[i]*=(ans[x]+1); 

		suf[i]%=m; 

	}

	upor[1]=1; 

	for(int i=1;i<=(int)v[s].size();i++)

	{

		int x=v[s][i-1]; 

		if(x==par) continue; 

		upor[x]=1; 

		upor[x]=(upor[x]*pre[i-1])%m; 

		upor[x]=(upor[x]*suf[i+1])%m; 

		upor[x]*=upor[s];  

		upor[x]++; 

		upor[x]%=m; 

		dfs1(x,s);

	}

}

int main()

{

	

	cin>>n>>m;

	for(int i=0;i<n-1;i++)

	{

		ll a,b; 

		cin>>a>>b;

		v[a].pb(b);

		v[b].pb(a);

	}

	dfs(1,-1);

	dfs1(1,-1);

	upor[1]=1; 

	for(int i=1;i<=n;i++) 

	{

		ans[i]=(ans[i]*upor[i])%m; 

		cout<<ans[i]<<endl; 

	}

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

using ll=long long;

using pii=pair<int,int>;

#define F first

#define S second

#define sz(x) int(x.size())

#define pb push_back



int mod,n;

vector<vector<int>> G;

vector<int> res,ans;

void dfs1(int u,int fa){

    res[u]=1;

    for(auto to:G[u]){

        if(to==fa) continue;

        dfs1(to,u);

        res[u]=ll(res[to]+1)*res[u]%mod;

    }

}

void dfs2(int root,int fa,ll now){

    ans[root]=((now+1)*res[root])%mod;

    vector<pii> pre,suf;

    for(auto to:G[root]){

        if(to==fa) continue;

        pre.pb({res[to]+1,to});

        suf.pb({res[to]+1,to});

    }

    for(int i=1;i<sz(pre);i++) pre[i].F=ll(pre[i-1].F)*pre[i].F%mod;

    for(int i=sz(suf)-2;i>=0;i--) suf[i].F=ll(suf[i+1].F)*suf[i].F%mod;

    for(int i=0;i<sz(pre);i++){

        ll l=(i==0?1:pre[i-1].F),r=(i==sz(pre)-1?1:suf[i+1].F);

        dfs2(pre[i].S,root,l*r%mod*(now+1)%mod);

    }

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    cin>>n>>mod;

    G.resize(n+1);

    res.resize(n+1);

    ans.resize(n+1);

    for(int i=0;i<n-1;i++){

        int x,y;

        cin>>x>>y;

        G[x].push_back(y);

        G[y].push_back(x);

    }

    dfs1(1,0);

    dfs2(1,0,0);

    for(int i=1;i<=n;i++){

        cout<<ans[i]<<endl;

    }

    return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



#define pb push_back

using namespace std;

typedef long long ll;

const int N = 100007;

vector<int> e[N];



ll f[N];

ll ans[N];

int m;



void solve(int u, int p = -1) {



	f[u] = 1;

	for(int v : e[u]) {

		if(v == p) continue;

		solve(v, u);



		f[u] = f[u] * f[v] % m;

	}



	f[u] = (f[u] + 1)%m;

}



void dfs(int u, int p = -1) {



	if(p != -1) { // adiciona f do pai

		f[u] = (f[u] - 1 + m)%m;

		f[u] = f[u] * f[p] % m;

		f[u] = (f[u] + 1)%m;

	}



	ans[u] = (f[u] - 1 + m)%m;



	vector<ll> suf(e[u].size() + 1, 1);

	for(int i = e[u].size()-1; i >= 0; --i) {

		suf[i] = suf[i+1] * f[e[u][i]] % m;

	}



	ll aux = 1;

	for(int i = 0; i < e[u].size(); i++) {

		int v = e[u][i];



		ll valor = f[v]; // valor antes de mudar, pra nao precisar remover o pai

		if(v != p) {

			// remove v

			f[u] = aux * suf[i + 1] % m;

			f[u] = (f[u] + 1)%m; 



			dfs(v, u);	

		}

		

		aux = aux * valor % m;

	}

}



int main() {

	ios::sync_with_stdio(0); cin.tie(0);



	int n; cin >> n >> m;



	for(int i = 0; i + 1 < n; i++) {

		int u, v; cin >> u >> v;

		e[u].pb(v);

		e[v].pb(u);

	}



	solve(1, -1);

	dfs(1, -1);



	for(int i = 1; i <= n; i++) {

		cout << ans[i] << '\n';

	}

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

using ll=long long;

using pii=pair<int,int>;

#define F first

#define S second

#define sz(x) int(x.size())

#define pb push_back



int mod,n;

vector<vector<int>> G;

vector<int> res,ans;

void dfs1(int u,int fa){

    res[u]=1;

    for(auto to:G[u]){

        if(to==fa) continue;

        dfs1(to,u);

        res[u]=ll(res[to]+1)*res[u]%mod;

    }

}

void dfs2(int root,int fa,ll now){

    ans[root]=((now+1)*res[root])%mod;

    vector<pii> pre,suf;

    for(auto to:G[root]){

        if(to==fa) continue;

        pre.pb({res[to]+1,to});

        suf.pb({res[to]+1,to});

    }

    for(int i=1;i<sz(pre);i++) pre[i].F=ll(pre[i-1].F)*pre[i].F%mod;

    for(int i=sz(suf)-2;i>=0;i--) suf[i].F=ll(suf[i+1].F)*suf[i].F%mod;

    for(int i=0;i<sz(pre);i++){

        ll l=(i==0?1:pre[i-1].F),r=(i==sz(pre)-1?1:suf[i+1].F);

        dfs2(pre[i].S,root,l*r%mod*(now+1)%mod);

    }

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    cin>>n>>mod;

    G.resize(n+1);

    res.resize(n+1);

    ans.resize(n+1);

    for(int i=0;i<n-1;i++){

        int x,y;

        cin>>x>>y;

        G[x].push_back(y);

        G[y].push_back(x);

    }

    dfs1(1,0);

    dfs2(1,0,0);

    for(int i=1;i<=n;i++){

        cout<<ans[i]<<endl;

    }

    return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

using namespace std;

int main()

{

	int a;

	cin>>a;

	cout<<"ABC"<<a<<endl;

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

int main(){

    int n;

    scanf("%d",&n);

    printf("ABC%d\n",n);

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int n;



int main(){

    cin>>n;

    cout<<"ABC"<<n;

    

    return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

int main(){

    int n;

    scanf("%d",&n);

    printf("ABC%d\n",n);

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

using namespace std;

int main()

{

    //string s;

    int s;

    cin >> s;

    cout << "ABC" << s << endl;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cmath>

int main()

{

    char str[20];

    scanf("%s",str);

    printf("ABC%s\n",str);

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



int main()

{

    int n;

    cin >> n;

    cout << "ABC" << n << endl;

    return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cmath>

int main()

{

    char str[20];

    scanf("%s",str);

    printf("ABC%s\n",str);

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

using namespace std;

int main(){

int n;

while(cin>>n){

    cout<<"ABC"<<n<<endl;

}

return 0;

}


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cmath>

int main()

{

    char str[20];

    scanf("%s",str);

    printf("ABC%s\n",str);

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

using namespace std;

int main()

{   int n;

while(cin>>n)

{

cout<<"ABC"<<n<<endl;

}

return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cmath>

int main()

{

    char str[20];

    scanf("%s",str);

    printf("ABC%s\n",str);

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cstdio>

using namespace std;

int main(){

    double a;

    while(cin>>a)

    {

        cout<<"ABC"<<a<<endl;

    }

    return 0;

    }


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cmath>

int main()

{

    char str[20];

    scanf("%s",str);

    printf("ABC%s\n",str);

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;



#define reps(i,j,n) for(int i = (j) ; i < (int)(n) ; ++i)    

#define rep(i,n) reps(i,0,n)  

#define each(it,c) for(__typeof (c).begin() it = (c).begin(); it != (c).end(); it++)  

  

#define all(v) (v).begin(), (v).end()  

#define pb(x) push_back(x)  

#define sz(x) (int)((x).size())  

#define UNQ(s) {sort(ALL(s));(s).erase(unique(ALL(s)),(s).end());}   

#define fr first  

#define sc second  

  

typedef pair< int , int > Pi;  

typedef pair< int , Pi > Pii;



  

typedef long long int64;  

const int INF = 1 << 30;  

  

template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1,T2>& a){ return is>>a.first>>a.second; }  

template<typename T1, typename T2> ostream& operator<<(ostream& os, pair<T1,T2>& a){ return os<<a.first<<" "<<a.second; }  

template<typename T> istream& operator>>(istream& is, vector< T >& vc){ rep(i,sz(vc)) is >> vc[i]; return is;}  

template<typename T> ostream& operator<<(ostream& os, vector< T >& vc){ rep(i,sz(vc)) os << vc[i] << endl; return os; }  



main(){

  int N, M, S, dp[50][3001];





  while(cin >> N >> M >> S, N){



    fill_n( *dp, 50 * 3001, 0);



    dp[0][0] = 1;



    for(int i = 1; i <= M; i++){

      for(int j = N * N; j > 0; j--){

        for(int k = S; k >= i; k--){ // マスまでの総和

          (dp[j][k] += dp[j - 1][k - i]) %= 100000;

        }

      }

    }



    cout << dp[N * N][S] << endl;

  }

  return(0);

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>  

using namespace std;



int main(){

  int N, M, S;

  while(cin >> N >> M >> S, N){

    // dp[i][j]: 場所iで今の合計がjのときの組み合わせ数

    vector < vector< int > > dp( N * N + 1, vector< int >( S + 1, 0));

    dp[0][0] = 1;

    for(int i = 1; i <= M; i++){ // 選ぶ数字

      for(int j = N * N; j >= 1; j--){ // idx

        for(int k = i; k <= S; k++){ // 合計

          (dp[j][k] += dp[j - 1][k - i]) %= 100000;

        }

      }

    }

    cout << dp[N * N][S] << endl;

  }

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>



using namespace std;

const int mod = 100000;



int dp[2][2001][3001];



int main(int argc, char const* argv[])

{

	int n, m, s;

	do{

			cin >> n >> m >> s;

			if(n == 0)break;

			for(int i = 0; i < n * n; i++){

					for(int j = 1; j <= m; j++){

							for(int k = 1; k <= s; k++){

									if(i == 1){

											if(j < k)dp[1][j][k] = 0;

											else dp[1][j][k] = 1;

									}

									dp[(i + 1) & 1][j][k] = dp[(i + 1) & 1][j-1][k];

									if(k -j >= 0)dp[(i + 1) & 1][j][k] += dp[i & 1][j-1][k-j];

									dp[(i + 1) & 1][j][k] %= mod;

									// cout << i << " " << j << " " << k << " " << dp[(i + 1) & 1][j][k] << endl;

							}

					}

			}

			cout << dp[(n*n) & 1][m][s] << endl;

	}while(true);

	return 0;

}




// Optimized solution to the same problem (faster):
#include <iostream>

#include <string>

#include <queue>

#include <vector>

#include <set>

#include <map>

#include <algorithm>

#include <utility>

#include <iomanip>



#define ll long long int

#define pb push_back

#define mk make_pair

#define pq priority_queue



using namespace std;

typedef pair<int, int> P;

typedef pair<ll, int> Pl;

const int inf = 1e9;

const ll linf = 1LL << 50;

int n, m, s;

const int mod = 1e5;

ll dp[2][2001][3001];



int main(int argc, char const* argv[])

{

	while(true){

			scanf("%d %d %d", &n, &m, &s);

			if(n == 0)break;

			int target = s - n * n * (n * n + 1) / 2;

			int sup = m - n * n;

			for(int i = 0; i < 2; i++){

					for(int j = 0; j <= sup; j++){

							for(int k = 0; k <= target; k++){

									if(j == 0 && k == 0)dp[i][j][k] = 1;

									else dp[i][j][k] = 0;

							}

					}

			}

			dp[0][0][0] = 1;

			for(int i = 0; i < n * n; i++){

					for(int j = 1; j <= sup; j++){

							for(int k = 1; k <= target; k++){

									dp[(i+1) & 1][j][k] = dp[i & 1][j][k];

									if(k - (n * n - i) >= 0)dp[(i+1) & 1][j][k] += dp[(i+1) & 1][j-1][k-(n * n - i)];

									dp[(i+1) & 1][j][k] %= mod;

							}

					}

			}

			int res = 0;

			for(int i = 0; i <= sup; i++)res = (res + dp[(n*n) & 1][i][target]) % mod;

			cout << res << endl;

	}

	return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;



#define REP(i,a,b) for(int i=a;i<(int)b;i++)

#define rep(i,n) REP(i,0,n)

#define all(c) (c).begin(), (c).end()

#define zero(a) memset(a, 0, sizeof a)

#define minus(a) memset(a, -1, sizeof a)

#define watch(a) { cout << #a << " = " << a << endl; }

template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }

template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }



typedef long long ll;

int const inf = 1<<29;



int dp[55][3030];



int main() {



  int const MOD = 100000;



  for(int N, M, S; cin >> N >> M >> S && (N|M|S);) {

    rep(i, 55) rep(j, 3030)

      dp[i][j] = 0;



    dp[0][0] = 1;



    REP(add, 1, M + 1) {

      for(int currIndex = N * N; currIndex >= 1; currIndex--) {

        for(int currSum = add; currSum <= S; currSum++) {

          (dp[currIndex][currSum] += dp[currIndex - 1][currSum - add]) %= MOD;

        }

      }

    }



    cout << dp[N*N][S] << endl;

  }

  

  return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>



using namespace std;



#define REP(i,a,b) for(int i=a;i<(int)b;i++)

#define rep(i,n) REP(i,0,n)

#define all(c) (c).begin(), (c).end()

#define zero(a) memset(a, 0, sizeof a)

#define minus(a) memset(a, -1, sizeof a)

#define watch(a) { cout << #a << " = " << a << endl; }

template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }

template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }



typedef long long ll;

int const inf = 1<<29;



int dp[55][3030];



int main() {



  int const MOD = 100000;



  for(int N, M, S; cin >> N >> M >> S && (N|M|S);) {

    rep(i, 55) rep(j, 3030)

      dp[i][j] = 0;



    dp[0][0] = 1;



    REP(i, 1, N * N + 1) {

      REP(j, i, S + 1) {

        dp[i][j] = (dp[i - 1][j - i] + dp[i][j - i]) % MOD;

        if(j >= M+1) {

          dp[i][j] -= dp[i - 1][j - M - 1];

          (dp[i][j] += MOD) %= MOD;

        }

      }

    }



    cout << dp[N*N][S] << endl;



  }

  

  return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstdio>

#include<algorithm>



using namespace std;



#define rep(i,n) for(int i=0;i<n;i++)

#define reps(i,n) for(int i=1;i<=n;i++)



int dp[50][2][3001];



int main(){

	

	while(1){

		int n,m,s;

		scanf("%d%d%d",&n,&m,&s);

		if(n==0)break;

		int t1=0,t2=1;

		n*=n;

		rep(i,50)rep(j,2)rep(k,s+1)dp[i][j][k]=0;

		dp[0][0][0]=1;

		reps(j,m){

			

			dp[0][t2][0]=1;

			

			reps(i,n){

				int nn=i;

				int st=(nn*(nn+1))/2;

				for(int k=st-1;k<s+1;k++){

					dp[i][t2][k]=0;

					if(k-j>=0){

						dp[i][t2][k]+=dp[i-1][t1][k-j];

					}

					dp[i][t2][k]+=dp[i][t1][k];

					if(dp[i][t2][k]<0)puts("AAAAAAA");

					dp[i][t2][k]%=100000;

				}

				/*

				if(i<9&&j<9){

					printf("%d %d\n",i,j);

					for(int k=0;k<50;k++){

						printf("%d ",dp[i][t2][k]);

					}puts("");

				}*/

			}

			swap(t1,t2);

		}

		

		printf("%d\n",dp[n][t1][s]);

	}

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>



using namespace std;



#define rep(i,n) for(i=0;i<n;i++)

#define reps(i,n) for(i=1;i<=n;i++)



int dp[50][2][3001];



int main(){

	

	int n,m,s,nn,st,i,j,k;

	int t1=0,t2=1;

	while(1){

		scanf("%d%d%d",&n,&m,&s);

		if(n==0)break;

		

		t1=0;

		t2=1;

		n*=n;

		rep(i,50)rep(j,2)rep(k,s+1)dp[i][j][k]=0;

		dp[0][0][0]=1;

		reps(j,m){

			

			dp[0][t2][0]=1;

			

			reps(i,n){

				nn=i;

				st=(nn*(nn+1))/2;

				int mm,pp,end;

				mm=(j-1)/2;

				if(j%2==0)pp=j/2;

				else pp=0;

				

				end= min(mm*(mm+1) + pp + st,s+1);

				

				for(k=st-1;k<=end;k++){

					dp[i][t2][k]=0;

					if(k-j>=0){

						dp[i][t2][k]+=dp[i-1][t1][k-j];

					}

					dp[i][t2][k]+=dp[i][t1][k];

					if(dp[i][t2][k]<0)puts("AAAAAAA");

					dp[i][t2][k]%=100000;

				}

				/*

				if(i<9&&j<12){

					printf("%d %d\n",i,j);

					for(int k=0;k<50;k++){

						printf("%d ",dp[i][t2][k]);

					}puts("");

				}*/

			}

			swap(t1,t2);

		}

		

		printf("%d\n",dp[n][t1][s]);

	}

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstdio>

#include<algorithm>



using namespace std;



#define rep(i,n) for(i=0;i<n;i++)

#define reps(i,n) for(i=1;i<=n;i++)



int dp[50][2][3001];



int main(){

	

	int n,m,s,nn,st,i,j,k;

	int t1=0,t2=1;

	while(1){

		scanf("%d%d%d",&n,&m,&s);

		if(n==0)break;

		

		t1=0;

		t2=1;

		n*=n;

		rep(i,50)rep(j,2)rep(k,s+1)dp[i][j][k]=0;

		dp[0][0][0]=1;

		reps(j,m){

			

			dp[0][t2][0]=1;

			

			reps(i,n){

				nn=i;

				st=(nn*(nn+1))/2;

				for(k=st-1;k<s+1;k++){

					dp[i][t2][k]=0;

					if(k-j>=0){

						dp[i][t2][k]+=dp[i-1][t1][k-j];

					}

					dp[i][t2][k]+=dp[i][t1][k];

					if(dp[i][t2][k]<0)puts("AAAAAAA");

					dp[i][t2][k]%=100000;

				}

				/*

				if(i<9&&j<9){

					printf("%d %d\n",i,j);

					for(int k=0;k<50;k++){

						printf("%d ",dp[i][t2][k]);

					}puts("");

				}*/

			}

			swap(t1,t2);

		}

		

		printf("%d\n",dp[n][t1][s]);

	}

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>



using namespace std;



#define rep(i,n) for(i=0;i<n;i++)

#define reps(i,n) for(i=1;i<=n;i++)



int dp[50][2][3001];



int main(){

	

	int n,m,s,nn,st,i,j,k;

	int t1=0,t2=1;

	while(1){

		scanf("%d%d%d",&n,&m,&s);

		if(n==0)break;

		

		t1=0;

		t2=1;

		n*=n;

		rep(i,50)rep(j,2)rep(k,s+1)dp[i][j][k]=0;

		dp[0][0][0]=1;

		reps(j,m){

			

			dp[0][t2][0]=1;

			

			reps(i,n){

				nn=i;

				st=(nn*(nn+1))/2;

				int mm,pp,end;

				mm=(j-1)/2;

				if(j%2==0)pp=j/2;

				else pp=0;

				

				end= min(mm*(mm+1) + pp + st,s+1);

				

				for(k=st-1;k<=end;k++){

					dp[i][t2][k]=0;

					if(k-j>=0){

						dp[i][t2][k]+=dp[i-1][t1][k-j];

					}

					dp[i][t2][k]+=dp[i][t1][k];

					if(dp[i][t2][k]<0)puts("AAAAAAA");

					dp[i][t2][k]%=100000;

				}

				/*

				if(i<9&&j<12){

					printf("%d %d\n",i,j);

					for(int k=0;k<50;k++){

						printf("%d ",dp[i][t2][k]);

					}puts("");

				}*/

			}

			swap(t1,t2);

		}

		

		printf("%d\n",dp[n][t1][s]);

	}

}

// Fastest known solution for this problem: