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

  * t0 = t1 = 0,
  * t2 = 1,
  * ti = ti - 1 + ti - 2 + ti - 3.



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

Input

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

Output

Output n-th tribonacci number modulo 26.

Examples

Input

4


Output

2


Input

9


Output

18

Source: codeforces | Difficulty: MEDIUM_HARD


Solutions: