Prime Permutations

A permutation of N distinct integers between 1 and N, both inclusive, is called a prime permutation of size N iff - for all i between 1 and N, the following condition holds: The ith integer is the Xth smallest integer in the first i integers, where X is either 1 or a prime number. Your task is to find out how many prime permutations are there of size N. Input The first line contains a single i