PatternLock | Topcoder Archive

Problem Statement

This problem is about a pattern lock similar to the one used on Android devices.

On the screen there is a set of nodes, placed onto vertices of a rectangular grid. (Android devices usually use a 3 times 3 grid, but we will use grids of different dimensions in this problem.) We will assign Cartesian coordinates to the nodes, starting with (0,0) in a corner.

To unlock the device, the user has to draw the correct pattern: a path that connects some of the nodes. Below we describe the properties of a valid pattern.

The pattern is a sequence of nodes.
There must be at least one node in the pattern.
Each node may only appear in the pattern at most once.
For any two consecutive nodes A and B in the pattern, each other node that lies on the straight line segment AB must occur in the pattern before A and B.

According to the last rule, (0,1)-(0,0)-(0,2) is a valid pattern: the segment (0,0)-(0,2) does contain another node (0,1) but that node was already used in the pattern. On the other hand, no valid pattern can start with the nodes (0,0) and (0,2).

You are given ints N and MOD. Alice's device has a grid of 2 times N nodes. (That is, the nodes have coordinates between (0,0) and (1,N-1), inclusive.) Alice wants to choose a pattern of length 2*N (i.e., the longest possible pattern). Let X be the number of different patterns she may choose. Return the value (X modulo MOD).

Definition

Class:: PatternLock
Method:: solve
Parameters:: int, int
Returns:: int
Method signature:: int solve(int N, int MOD)
(be sure your method is public)

Notes

Two patterns are considered the same only if they contain nodes in exactly the same order.

Constraints

N will between 1 and 3500, inclusive.
MOD will between 2 and 1,000,000,007 (10^9+7), inclusive.

Examples

```
1
```
```
12345667
```
```
Returns: 2
```
There are only two possible patterns: (0,0)-(1,0) and (1,0)-(0,0).
```
2
```
```
324124124
```
```
Returns: 24
```
All 4! permutations of the 4 nodes give us valid patterns of length 4.
```
3
```
```
5325352
```
```
Returns: 504
```
In this case some of the 6! possible permutations are illegal. For example, this is not a valid pattern: (0,0)-(0,2)-(0,1)-(1,0)-(1,2)-(1,1).
```
500
```
```
1000000007
```
```
Returns: 286169049
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.