Problem Statement
Many websites force their users to select passwords that satisfy various annoying constraints. This is not only annoying but also dumb, as it often makes the passwords less secure: users who cannot remember their password are prone to storing it in an insecure way.
The authors of these annoying systems often claim that they do it to increase the space of possible passwords. In this problem we will look at this claim and count some annoying passwords.
An annoying password has the following properties:
- It contains exactly U uppercase letters ('A'-'Z').
- It contains exactly L lowercase letters ('a'-'z').
- It contains exactly D digits ('0'-'9').
- It does not contain any other characters.
- No two characters of the same type (uppercase, lowercase, digits) are adjacent.
- All characters in the password are distinct.
Given U, L and D, count all annoying passwords and return their count modulo 10^9 + 7.
Definition
- Class:
- AnnoyingPasswords
- Method:
- count
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int count(int U, int L, int D)
- (be sure your method is public)
Notes
- There are 26 different letters (both in uppercase and in lowercase), and there are 10 different digits.
Constraints
- U will be between 0 and 26, inclusive.
- L will be between 0 and 26, inclusive.
- D will be between 0 and 10, inclusive.
Examples
4
1
1
Returns: 0
The password should contain 4 uppercase letters, 1 lowercase letter and 1 digit. There are no such annoying passwords: regardless of what order of characters we'll choose, there will always be two consecutive uppercase letters somewhere in the password, and that's not allowed.
5
0
4
Returns: 783743727
The uppercase letters and digits must alternate. For example, "A1B2C3D4Z" is a valid annoying password. There are exactly 39,783,744,000 annoying passwords, the return value is the remainder this number gives when divided by 10^9 + 7.
1
1
1
Returns: 40560
Here, the answer is the exact number of annoying passwords (as it is smaller than 10^9 + 7).
2
2
3
Returns: 559599923
Some annoying passwords of this type include "a1b2C3D" and "7gG4Pp2".
0
0
0
Returns: 1
There is exactly one empty password. By definition, it is annoying.
2
3
4
Returns: 342371741
2
4
3
Returns: 553507145
26
26
10
Returns: 518946544
5
2
3
Returns: 10062185
3
3
5
Returns: 745878943
2
5
2
Returns: 653580610
11
2
6
Returns: 0
17
14
9
Returns: 606647545
10
8
8
Returns: 702403230
12
12
9
Returns: 94472236
1
25
6
Returns: 0
21
0
1
Returns: 0
0
8
7
Returns: 987721616
23
17
0
Returns: 0
26
10
9
Returns: 0
13
7
3
Returns: 0
16
16
5
Returns: 638849638
14
7
0
Returns: 0
17
11
5
Returns: 789284290
19
10
8
Returns: 658760173
18
24
3
Returns: 0
7
25
0
Returns: 0
4
10
1
Returns: 0
11
18
6
Returns: 633746275
16
17
4
Returns: 681275379
3
20
3
Returns: 0
22
10
3
Returns: 0
15
23
1
Returns: 0
24
13
9
Returns: 0
11
21
4
Returns: 0
24
25
3
Returns: 177219232
25
17
4
Returns: 0
11
17
9
Returns: 604942699
1
15
4
Returns: 0
18
24
6
Returns: 731050724
8
23
8
Returns: 0
25
7
9
Returns: 0
3
20
3
Returns: 0
12
15
4
Returns: 735693606
19
17
2
Returns: 899163447
14
0
2
Returns: 0
17
20
1
Returns: 0
2
8
8
Returns: 939804261
26
19
8
Returns: 795695120
15
25
6
Returns: 0
11
24
0
Returns: 0
1
0
0
Returns: 26
0
1
0
Returns: 26
0
0
1
Returns: 10
20
20
8
Returns: 163244154
26
15
10
Returns: 547361592
13
13
7
Returns: 42303229