Let C be a class of relational structures. We denote by f C (n) the number of structures in C over the labeled set {0,...,n-1}. For any C definable in monadic second-order logic with unary and binary relation symbols only, E. Specker and C. Blatter showed that for every m N, the function f C satisfies a linear recurrence relation modulo m, and hence it is ultimately periodic modulo m. The case of ternary relation symbols, and more generally of arity k symbols for k>=3, was left open.In this paper we show that for every m there is a class of structures C m , which is definable even in first-order logic with one quaternary (arity four) relation symbol, such that fC m is not ultimately periodic modulo m. This shows that the Specker-Blatter Theorem does not hold for quaternary relations, leaving only the ternary case open.