This question was recently asked in Samsung "Code The Next" contest hosted on hackererth.

Boogle, the software giant developed a mobile operating system named Ambroid. As we all know, in order to unlock an Ambroid device, one needs to draw a pattern connecting the given dots. The developers of Ambroid OS want this pattern unlock to be more secure. So they are wondering, in how many ways, can we draw a pattern by connecting dots.

Given N points (dots) in the co-ordinate system, find and return the number of ways in which, we can draw a pattern by connecting dots.

A pattern is a sequence of distinct dots where two adjacent dots in the sequence are connected by a line segment and should satisfy following conditions.

• A pattern should connect at least two dots.
• While connecting two dots A and B, suppose there is a dot C which has not yet been connected and lies on the line segment joining A and B, then you cannot connect A and B without connecting C in between, that is, pattern A-C-B and pattern B-C-A are valid but the patterns A-B or B-A are not valid as C has not yet been connected.

Input 2<=N<=16 0<=x,y<=200

I only know the obvious n! solution. Any solution with better time complexity is appreciated.