题目描述

小明最近学习了组合数，从 n 个元素中任取 i 个元素一组，其可能的方案数表示为 C(n,i) 。假如 i 取从 0 到 n 的所有偶数，他想知道所有 C(n,i) 的和是多少。

由于答案可能很大，请输出答案对 123456 的余数。

输入格式

一个整数 n 。

输出格式

一个整数，即为答案。

样例

3

4

样例解释

对于 30% 的数据， n ≤ 20 ;

对于 100% 的数据， n ≤ 1000 。