```go
package main

import (
	"bufio"
	"fmt"
	"os"
)

func readInt(r *bufio.Reader) int {
	var res int
	b, err := r.ReadByte()
	for err == nil && (b < '0' || b > '9') {
		b, err = r.ReadByte()
	}
	for err == nil && b >= '0' && b <= '9' {
		res = res*10 + int(b-'0')
		b, err = r.ReadByte()
	}
	return res
}

func readInt64(r *bufio.Reader) int64 {
	var res int64
	b, err := r.ReadByte()
	for err == nil && (b < '0' || b > '9') {
		b, err = r.ReadByte()
	}
	for err == nil && b >= '0' && b <= '9' {
		res = res*10 + int64(b-'0')
		b, err = r.ReadByte()
	}
	return res
}

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	n := readInt(reader)
	m := readInt(reader)
	k := readInt64(reader)

	adj := make([][]int, n+1)
	for i := 0; i < m; i++ {
		u := readInt(reader)
		v := readInt(reader)
		adj[u] = append(adj[u], v)
	}

	dfn := make([]int, n+1)
	low := make([]int, n+1)
	inStack := make([]bool, n+1)
	stack := make([]int, 0, n)
	timer := 0

	val := make([]int, n+1)
	for i := range val {
		val[i] = -1
	}
	inSCC := make([]bool, n+1)

	var ans int64

	var dfs func(u int)
	dfs = func(u int) {
		timer++
		dfn[u] = timer
		low[u] = timer
		stack = append(stack, u)
		inStack[u] = true

		for _, v := range adj[u] {
			if dfn[v] == 0 {
				dfs(v)
				if low[v] < low[u] {
					low[u] = low[v]
				}
			} else if inStack[v] {
				if dfn[v] < low[u] {
					low[u] = dfn[v]
				}
			}
		}

		if low[u] == dfn[u] {
			var scc []int
			for {
				v := stack[len(stack)-1]
				stack = stack[:len(stack)-1]
				inStack[v] = false
				scc = append(scc, v)
				if u == v {
					break
				}
			}

			if len(scc) == 1 {
				hasSelf := false
				for _, v := range adj[scc[0]] {
					if v == scc[0] {
						hasSelf = true
						break
					}
				}
				if !hasSelf {
					return
				}
			}

			for _, v := range scc {
				inSCC[v] = true
			}

			d := 0
			q := make([]int, 0, len(scc))
			q = append(q, scc[0])
			val[scc[0]] = 0

			for len(q) > 0 {
				curr := q[0]
				q = q[1:]

				for _, nxt := range adj[curr] {
					if !inSCC[nxt] {
						continue
					}
					if val[nxt] == -1 {
						val[nxt] = val[curr] + 1
						q = append(q, nxt)
					} else {
						diff := abs(val[curr] + 1 - val[nxt])
						d = gcd(d, diff)
					}
				}
			}

			if d > 0 {
				kMod := int(k % int64(d))
				if (2*kMod)%d == 0 {
					freq := make([]int, d)
					for _, v := range scc {
						freq[val[v]%d]++
					}

					if kMod == 0 {
						for i := 0; i < d; i++ {
							ans += int64(freq[i]) * int64(freq[i]+1) / 2
						}
					} else {
						for i := 0; i < d/2; i++ {
							ans += int64(freq[i]) * int64(freq[i+d/2])
						}
					}
				}
			}

			for _, v := range scc {
				inSCC[v] = false
				val[v] = -1
			}
		}
	}

	for i := 1; i <= n; i++ {
		if dfn[i] == 0 {
			dfs(i)
		}
	}

	fmt.Println(ans)
}
```