Vera owns N tops and N pants. The i-th top and i-th pants have colour i, for 1 ≤ i ≤ N, where all N colors are different from each other.

An outfit consists of one top and one pants. Vera likes outfits where the top and pants are not the same colour.

How many different outfits does she like?

Constraints:

1 ≤ N ≤ 2017

N is integer

Vera is learning about the longest common subsequence problem.

A string is a (possibly empty) sequence of lowercase letters. A subsequence of a string S is a string obtained by deleting some letters of S (possibly none or all). For example "vra", "a", "", and "vera" are all subsequences of "vera". The longest common subsequence (LCS) of two strings A, B is a string that is a subsequence of A and B and has the maximum length among all strings that are a subsequence of A and B. There could be multiple LCS for two given strings. For example a LCS of "vera" and "eats" is "ea".

For homework she was given two strings A, B, both of length N and she had to determine the length of the LCS of A and B. She determined the answer to be K but lost B. Given A and K, help her find a possible value of B. It's possible that Vera may have made a mistake and no such B exists, in that case output "WRONGANSWER" (without quotes).

Constraints:

1 ≤ N ≤ 2000

0 ≤ K ≤ 2000

N, K are integers

A consists of N lowercase letters

The harmonic mean of a sequence of positive integers x₁, ..., x_N is

Vera thinks that an array of positive integers A = [A₁, ..., A_N] of length N is K-mean-sorted if M(i) ≥ M(i + 1) for 1 ≤ i ≤ N - K where

A permutation P is an ordered set of integers P₁, P₂, ..., P_N, consisting of N distinct positive integers, each of them doesn't exceed N. We'll call number N the size or the length of permutation.

Permutation P is lexicographically smaller than permutation Q if there is i (1 ≤ i ≤ n), such that P_i < Q_i, and for any j (1 ≤ j < i) P_j = Q_j.

Given integers N and K, help Vera find the lexicographically smallest permutation P of integers 1 to N such that P is K-mean-sorted but not L-mean-sorted for 1 ≤ L ≤ N - 1, L ≠ K.

If no such permutation exists output 0.

Constraints:

2 ≤ N ≤ 100

1 ≤ K ≤ N - 1

N, K are integers

Vera is very smart and invented a new sorting algorithm. She coded the following python function to count how many steps her algorithm takes.

def steps(array):
  if len(array) == 0:
    return 0
  pivot = array[0]
  count = 0
  lesser = []
  greater = []
  for element in array:
    count += 1
    if element < pivot:
      lesser.append(element)
    elif element > pivot:
      greater.append(element)
  return count + steps(lesser) + steps(greater)

A permutation P is an ordered set of integers P₁, P₂, ..., P_N, consisting of N distinct positive integers, each of them doesn't exceed N. We'll call number N the size or the length of permutation.

You are given integers N and K.

Help Vera count the number of permutations P of size N such that steps(P) = K. This number could be large, so output it modulo 10⁹ + 7.

Constraints:

1 ≤ N ≤ 30

1 ≤ K ≤ 900

N, K are integers

Vera has N friends numbered from 0 to N - 1. Being in Software Engineering, all her friends do not have enough spare time to engage in relationships. However, friends have crushes on each other.

Let g(x), where x are non-negative integers, be the number of ones in the binary representation of x.

Let f(i, j) = g((A·B^{(i·N + j)})%M), where A, B, M are integer constants.

It is known that for any 2 friends i < j, if f(i, j) is even then i has a crush on j, otherwise j has a crush on i.

Vera thinks love triangles are very funny. A love triangle is a set of 3 friends i, j, k such that i has a crush on j, j has a crush on k and k has a crush on i.

Given integers N, M, A, B tell Vera how many love triangles exist among her friends. Two love triangles are different if they contain a different set of 3 friends.

Constraints:

3 ≤ N, M ≤ 200, 000

0 < A, B < M

N, M, A, B are integers

M is prime