  Let $p$ be a prime, and let $f(x)$ be an integer-valued polynomial. By a
combinatorial approach, we obtain a nontrivial lower bound of the $p$-adic
order of the sum $$\sum_{k=r(mod p^{\beta})}\binom{n}{k}(-1)^k
f([(k-r)/p^{\alpha}]),$$ where $\alpha\ge\beta\ge 0$, $n\ge p^{\alpha-1}$ and
$r\in Z$. This polynomial extension of Fleck's congruence has various
backgrounds and several consequences such as $$\sum_{k=r(mod
p^\alpha)}\binom{n}{k} a^k\equiv 0 (mod
p^{[(n-p^{\alpha-1})/\phi(p^\alpha)]})$$ provided that $\alpha>1$ and
$a\equiv-1(mod p)$.
