import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
  private final int nChars;
  private int count = 0;
  private Map<Task,BigInteger> memo = new HashMap<>();
  
  public Main(int nChars) {
    this.nChars = nChars;
  }
  /*+******************************************************************/  
  private static class Task {
    public final int strlen;
    public final int unpaired;

    Task(int strlen, int unpaired) {
      this.strlen = strlen;
      this.unpaired = unpaired;
    }
    @Override
    public int hashCode() {
      return strlen*117 ^ unpaired;
    }
    @Override
    public boolean equals(Object other) {
      if (!(other instanceof Task)) {
        return false;
      }
      Task t2 = (Task)other;
      return strlen==t2.strlen && unpaired==t2.unpaired;
    }
    @Override
    public String toString() {
      return "("+strlen+","+unpaired+")";
    }
  }
  /*+******************************************************************/  
  private BigInteger getMemoed(Task t) {
    //System.out.println("getMemoed"+t);
    if (t.strlen==0 || t.unpaired<0 || t.unpaired>t.strlen || t.unpaired>nChars
        || t.strlen%2 != t.unpaired%2) {
      return BigInteger.valueOf(0);
    }
    
    if (t.strlen==1) {
      return BigInteger.valueOf(nChars);
    }
    return memo.get(t);
  }
  /*+******************************************************************/  
  public int getCount() {
    return count;
  }
  public BigInteger computeNDeep(Task t) {
    List<Task> stack = new ArrayList<Task>();
    BigInteger result = null;
    stack.add(t);
    
    while (stack.size()>0) {
      count += 1;
      t = stack.remove(stack.size()-1);
      //System.out.println("removed "+t);
      result = getMemoed(t);
      if (result!=null) {
        continue;
      }
      
      Task t1 = new Task(t.strlen-1, t.unpaired+1);
      BigInteger r1 = getMemoed(t1);
      Task t2 = new Task(t.strlen-1, t.unpaired-1);
      BigInteger r2 = getMemoed(t2);
      if (r1==null) {
        stack.add(t);
        stack.add(t1);
        if (r2==null) {
          stack.add(t2);
        }
        continue;
      }
      if (r2==null) {
        stack.add(t);
        stack.add(t2);
        continue;
      }
      result = compute(t1.unpaired, r1, nChars-t2.unpaired, r2);
      memo.put(t,  result);
      //System.out.println(""+t1+":"+r1+", "+t2+":"+r2+"  memo "+t+" = "+result);
    }
    return result;
  }
  private BigInteger compute(int u1, BigInteger r1, int u2, BigInteger r2) {
    r1 = r1.multiply(BigInteger.valueOf(u1));
    r2 = r2.multiply(BigInteger.valueOf(u2));
    return r1.add(r2);
  }
  public static void main(String[] argv) {
    argv = new String[] {"500", "4"};
    int strlen = Integer.parseInt(argv[0]);
    int nChars = Integer.parseInt(argv[1]);

    Main eps = new Main(nChars);
    
    BigInteger result = eps.computeNDeep(new Task(strlen, 0));
    System.out.printf("%d: N(%d, %d, 0) = %d%n", 
                      eps.getCount(), strlen, nChars, 
                      result); 
  }
}