Tribonacci numbers are a sequence of numbers, defined as follows:

• t₀ = t₁ = 0,
• t₂ = 1,
• t_i = t_i - 1 + t_i - 2 + t_i - 3.

You are given n; calculate n-th tribonacci number modulo 26.

The only line of input contains an integer n (1 ≤ n ≤ 1000).

Output n-th tribonacci number modulo 26.