Mongolian Mathematical Olympiad

1	2	3
4	5	6
7	8	9

Denote $A_i$, $i=1,2,4,5$ colourings such that there is at least one red square left up corner of which at one of $1,2,4,5$. Therefore by inclusion-exclusion principle number of such colourings equals to $$\begin{gathered} |A|=|A_1|+|A_2|+|A_4|+|A_5|-\sum |A_i\cap A_j|+ \\ +\sum |A_i\cap A_j\cap A_k|-|A_1\cap A_2\cap A_4\cap A_5| \end{gathered}$$ Thus $|A|=4\cdot 2^5-(4\cdot 2^3+2\cdot 2^2)+4\cdot 2-1=95$ and desired number is $512-95=417$.