package main

import (
	"fmt"
)

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

func lcm(a, b int) int {
	if a == 0 || b == 0 {
		return 0
	}
	return (a / gcd(a, b)) * b
}

type Matrix [][]int

func mul(A, B Matrix, size int) Matrix {
	C := make(Matrix, size)
	for i := 0; i < size; i++ {
		C[i] = make([]int, size)
		for k := 0; k < size; k++ {
			if A[i][k] == 0 {
				continue
			}
			for j := 0; j < size; j++ {
				C[i][j] = (C[i][j] + A[i][k]*B[k][j]) % 12345
			}
		}
	}
	return C
}

func power(A Matrix, p int64, size int) Matrix {
	res := make(Matrix, size)
	for i := 0; i < size; i++ {
		res[i] = make([]int, size)
		res[i][i] = 1
	}
	base := A
	for p > 0 {
		if p%2 == 1 {
			res = mul(res, base, size)
		}
		base = mul(base, base, size)
		p /= 2
	}
	return res
}

func main() {
	var n int64
	var c int
	if _, err := fmt.Scan(&n, &c); err != nil {
		return
	}

	conds := make([][]int, 26)
	for i := 0; i < c; i++ {
		var s string
		var m int
		fmt.Scan(&s, &m)
		charIdx := s[0] - 'A'
		conds[charIdx] = append(conds[charIdx], m)
	}

	L := make([]int, 26)
	for i := 0; i < 26; i++ {
		L[i] = 1
		if len(conds[i]) > 0 {
			L[i] = conds[i][0]
			for j := 1; j < len(conds[i]); j++ {
				L[i] = lcm(L[i], conds[i][j])
			}
		}
	}

	S := 1
	for i := 0; i < 26; i++ {
		if len(conds[i]) > 0 {
			S *= L[i]
		}
	}

	M := make(Matrix, S)
	for i := 0; i < S; i++ {
		M[i] = make([]int, S)
	}

	for s := 0; s < S; s++ {
		tuple := make([]int, 26)
		temp := s
		for i := 0; i < 26; i++ {
			if len(conds[i]) > 0 {
				tuple[i] = temp % L[i]
				temp /= L[i]
			}
		}

		for i := 0; i < 26; i++ {
			if len(conds[i]) > 0 {
				ntuple := make([]int, 26)
				copy(ntuple, tuple)
				ntuple[i] = (ntuple[i] + 1) % L[i]

				ns := 0
				mult := 1
				for j := 0; j < 26; j++ {
					if len(conds[j]) > 0 {
						ns += ntuple[j] * mult
						mult *= L[j]
					}
				}
				M[s][ns] = (M[s][ns] + 1) % 12345
			}
		}
	}

	res := power(M, n, S)

	ans := 0
	for s := 0; s < S; s++ {
		tuple := make([]int, 26)
		temp := s
		for i := 0; i < 26; i++ {
			if len(conds[i]) > 0 {
				tuple[i] = temp % L[i]
				temp /= L[i]
			}
		}

		valid := true
		for i := 0; i < 26; i++ {
			if len(conds[i]) > 0 {
				sat := false
				for _, m := range conds[i] {
					if tuple[i]%m == 0 {
						sat = true
						break
					}
				}
				if !sat {
					valid = false
					break
				}
			}
		}

		if valid {
			ans = (ans + res[0][s]) % 12345
		}
	}

	fmt.Println(ans)
}