Tri-Isomorphism

Source: UVa

Version: Phuoc Hung OJ Extended

Problem Statement

A simple graph has neither loops nor multiple edges. Two graphs are isomorphic if there is a bijection between their vertex sets that preserves adjacency.

$K_n$ denotes the complete graph on $n$ vertices, so every pair of distinct vertices is connected by an edge.

A decomposition of a graph is a list of subgraphs in which every edge of the original graph appears in exactly one subgraph.

Given $n$, determine whether $K_n$ can be decomposed into exactly three pairwise-isomorphic subgraphs.

Input

One positive integer $n$.

Output

Print YES if such a decomposition exists; otherwise print NO.

Subtasks

• Subtask 1 (20%): $n\le20$.
• Subtask 2 (30%): $21\le n\le100$ and $n\equiv0$ or $1\pmod3$.
• Subtask 3 (50%): Full constraints: $1\le n\le100$.

Examples

Input

4

Output

YES

Explanation

$K_4$ has $\binom42=6$ edges. They can be partitioned into three edge sets of size $2$ whose subgraphs are isomorphic, so the answer is YES.