stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#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; 

	}

}


// Faster C++ solution for the same problem (measured speedup: 6.332270554230943x):
#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;

}
// Slower C++ solution:
#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';

	}

}

// Faster C++ solution for the same problem (measured speedup: 3.4849333447878132x):
#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;

}
// Slower C++ solution:
#include<iostream>

using namespace std;

int main()

{

	int a;

	cin>>a;

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

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.266934175606231x):
#include<cstdio>

int main(){

    int n;

    scanf("%d",&n);

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

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int n;



int main(){

    cin>>n;

    cout<<"ABC"<<n;

    

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.260168196084547x):
#include<cstdio>

int main(){

    int n;

    scanf("%d",&n);

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

    return 0;

}
// Slower C++ solution:
#include <iostream>

using namespace std;

int main()

{

    //string s;

    int s;

    cin >> s;

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

}

// Faster C++ solution for the same problem (measured speedup: 5.321745612932373x):
#include<cstdio>

#include<cmath>

int main()

{

    char str[20];

    scanf("%s",str);

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

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



int main()

{

    int n;

    cin >> n;

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

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.321745612932373x):
#include<cstdio>

#include<cmath>

int main()

{

    char str[20];

    scanf("%s",str);

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

    return 0;

}
// Slower C++ solution:
#include <iostream>

using namespace std;

int main(){

int n;

while(cin>>n){

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

}

return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.323810041288996x):
#include<cstdio>

#include<cmath>

int main()

{

    char str[20];

    scanf("%s",str);

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

    return 0;

}
// Slower C++ solution:
#include<iostream>

using namespace std;

int main()

{   int n;

while(cin>>n)

{

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

}

return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.323810041288996x):
#include<cstdio>

#include<cmath>

int main()

{

    char str[20];

    scanf("%s",str);

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

    return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstdio>

using namespace std;

int main(){

    double a;

    while(cin>>a)

    {

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

    }

    return 0;

    }


// Faster C++ solution for the same problem (measured speedup: 5.435011444256779x):
#include<cstdio>

#include<cmath>

int main()

{

    char str[20];

    scanf("%s",str);

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

    return 0;

}
// Slower C++ solution:
#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);

}

// Faster C++ solution for the same problem (measured speedup: 1.0240208683085914x):
#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;

  }

}
// Slower C++ solution:
#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;

}




// Faster C++ solution for the same problem (measured speedup: 1.6790822851425113x):
#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;

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.58367259687117x):
#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;

}
// Slower C++ solution:
#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]);

	}

}

// Faster C++ solution for the same problem (measured speedup: 1.262614963881695x):
#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]);

	}

}
// Slower C++ solution:
#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]);

	}

}

// Faster C++ solution for the same problem (measured speedup: 1.262614963881695x):
#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]);

	}

}
// Slower C++ solution:


//y09-6 ビンゴ(2回目)

#include <iostream>

#include <fstream>

#include <stdio.h>

#include <math.h>

#include <time.h>

#include <string>

#include <vector>

#include <map>

#include <list>

#include <set>

#include <stack>

#include <queue>

#include <cstdlib>

#include <algorithm>

#include <random>

#include <cassert>

using namespace std;

#define LL long long

#undef INT_MIN

#undef INT_MAX

#define INT_MIN -2147483648

#define INT_MAX 2147483647

#define LL_MIN -9223372036854775808

#define LL_MAX 9223372036854775807

#define segment_size 65536

#define ROOP() while (true)



int main(){

    ROOP(){

        int N,M,S;

        cin >> N >> M >> S;

        if(N==0) return 0;



        int dp[50][3001];

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

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

                dp[i][j] = 0;

            }

        }

        dp[0][0] = 1;



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

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

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

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

                    dp[j][k] %= 100000;

                }

            }

        }

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



    }

    return 0;

}






// Faster C++ solution for the same problem (measured speedup: 1.6216382197504933x):


//y09-6 ビンゴ(2回目)

#include <iostream>

#include <fstream>

#include <stdio.h>

#include <math.h>

#include <time.h>

#include <string>

#include <vector>

#include <map>

#include <list>

#include <set>

#include <stack>

#include <queue>

#include <cstdlib>

#include <algorithm>

#include <random>

#include <cassert>

using namespace std;

#define LL long long

#undef INT_MIN

#undef INT_MAX

#define INT_MIN -2147483648

#define INT_MAX 2147483647

#define LL_MIN -9223372036854775808

#define LL_MAX 9223372036854775807

#define segment_size 65536

#define ROOP() while (true)



int main(){

    ROOP(){

        int N,M,S;

        cin >> N >> M >> S;

        if(N==0) return 0;

        M = min(M,S);



        int dp[50][3001];

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

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

                dp[i][j] = 0;

            }

        }

        dp[0][0] = 1;



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

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

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

                if(j>M) dp[i][j] -= dp[i-1][j-M-1];

                dp[i][j] %= 100000;

                if(dp[i][j]<0) dp[i][j]+=100000;

            }

        }

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



    }

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



using int64 = long long;

const int64 INF = 1LL << 62;



struct UnionFind

{

  vector< int > data;



  UnionFind(int sz)

  {

    data.assign(sz, -1);

  }



  bool unite(int x, int y)

  {

    x = find(x), y = find(y);

    if(x == y) return (false);

    if(data[x] > data[y]) swap(x, y);

    data[x] += data[y];

    data[y] = x;

    return (true);

  }



  int find(int k)

  {

    if(data[k] < 0) return (k);

    return (data[k] = find(data[k]));

  }



  int size(int k)

  {

    return (-data[find(k)]);

  }

};



int main()

{

  int N, M, A[100000], B[100000];



  cin >> N >> M;

  UnionFind uf(N);

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

    cin >> A[i] >> B[i];

    --A[i], --B[i];

    uf.unite(A[i], B[i]);

  }



  bitset< 100001 > dp;

  dp[uf.size(0)] = true;

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

    if(uf.find(i) == uf.find(1)) continue;

    if(uf.find(i) == uf.find(0)) continue;

    if(uf.find(i) != i) continue;

    dp |= dp << uf.size(i);

  }



  int64 ret = -INF;

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

    if(dp[i]) {

      int64 j = N - i;

      ret = max(ret, i * (i - 1) / 2 + j * (j - 1) / 2);

    }

  }



  cout << ret - M << endl;

}

// Faster C++ solution for the same problem (measured speedup: 2.00278668563405x):
#include <bits/stdc++.h>

using namespace std;



int main() {

    int n, m;

    cin >> n >> m;

    vector<vector<int>> adj(n);

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

        int a, b;

        cin >> a >> b;

        a--, b--;

        adj[a].push_back(b);

        adj[b].push_back(a);

    }



    vector<bool> visited(n);



    function<void(int)> dfs = [&](int v) {

        visited[v] = true;

        for (int a : adj[v]) {

            if (!visited[a]) {

                dfs(a);

            }

        }

    };



    int cnt1 = 0, cnt2 = 0;

    dfs(0);

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

        if (visited[i]) cnt1++;

    }

    dfs(1);

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

        if (visited[i]) cnt2++;

    }

    cnt2 -= cnt1;

    int rem = n - (cnt1 + cnt2);

    (cnt1 >= cnt2 ? cnt1 : cnt2) += rem;

    long long es = 1ll * cnt1 * (cnt1 - 1) / 2 + 1ll * cnt2 * (cnt2 - 1) / 2;

    cout << es - m << endl;

}