• [E] Eating Corns

  • 时间限制: 2000 ms 内存限制: 65535 K
  • 问题描述
  • Oh Jesus! Mr. Cai makes TT angry! So TT decide to not eat Chinese Cabbage. Instead, she eats corns.
    After TT ate up all the corns, the corn leaves scattered all over the floor.

    With this scene, TT forgot her unpleasant gradually. She start to play with these leaves.
    There are N left leaves and N right leaves. TT wants to put them into one line. What's more, she wants the line to be symmetrical. You can consider all the left leaves are the same and all the right leaves are the same.
    How many diffrient method can TT make a line?

    symmetrical. And an left leaf and an right leaf should make a pair like a pair of brackets. And if you choose one order of pair "()" or ")(" in one solution, you can't change it at this solution.

    So the solution below are valid:

    ()()()

    ((()))

    (()())

    )()()(

    )))(((

    ))()((

    And the solution below are invalid:

    ())(()

  • 输入
  • This problem contains several cases.
    Each case is an integer N (1 <= N <= 1 000 000).
  • 输出
  • For each case, output the answer mod 8644325.
  • 样例输入
  • 4
    
  • 样例输出
  • 12
    
  • 提示
  • 来源
  • XadillaX
  • 操作

显示春菜