Petr's problem P78605


Statement
 

pdf   zip

html

A permutation p1, …, pn is a sequence of numbers between 1 and n such that each number appears exactly once. An inversion in a permutation is a pair of indices (i, j) such that i < j but pi > pj. The weight of an inversion (i, j) is ji.

How many permutations of n elements exist where the sum of weights of all inversions is equal to x? For instance, there are exactly two such permutations for n = 4 and x = 4: 3, 2, 1, 4 and 1, 4, 3, 2.

Input

Input consists of several cases, each one with n and x. You can assume 1 ≤ n ≤ 14 and 0 ≤ x ≤ (n + 1)n(n − 1)/6.

Output

For every case, print the number of permutations of n elements such that the sum of weights of all inversions is x.

Public test cases
  • Input

    4 4
    1 0
    14 455
    14 200
    

    Output

    2
    1
    1
    486253544
    
  • Information
    Author
    Petr Mitrichev
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Novè Concurs de Programació de la UPC - Final
    Date
    2011-09-21