|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||512 MB||4||4||4||100.000%|
Following on from the engineering success of Left Pad, Ltd, Lynn started a new venture: Internet of Security, Inc. The company’s flagship product will be a device for entering passcodes.
The chief innovation of this device will be in its ability to reject attempts to set insecure passwords. An insecure passcode is defined as a sequence of digit presses such that at least two consecutive presses are either directly or diagonally adjacent.
Lynn, ever-vigilant for the future, is worried that this system might not allow enough unique passcodes to support a large company with trillions of employees. For a given digit pad grid size, and fixed length of password, calculate the number of allowed passwords.
Since the number might be very large in some cases, output your answer mod 1 000 000 007.
Output the number of legal passcodes, mod 1 000 000 007.
3 3 2
100 1 5
49 97 191