struct B{
	int v;
	B():v(0){}
	B(int v):v(v){}
	B operator+(B b){
		return B(v|b.v);
	}
	B operator*(B b){
		return B(v&b.v);
	}
	void operator+=(B b){
		v|=b.v;
	}
};

{
	int @n,@m;
	ll @t;
	Matrix<B> c(n,n);
	rep(m){
		int @a,@b;
		c[b][a].v=1;
	}
	c**=t;
	wt(sum[i,0,n](c[i][0].v));
}