bowang0911/leetcode huggingface dataset:
Analyze User Website Visit Pattern

You are given two string arrays `username` and `website` and an integer array `timestamp`. All the given arrays are of the same length and the tuple `[username[i], website[i], timestamp[i]]` indicates that the user `username[i]` visited the website `website[i]` at time `timestamp[i]`.

A **pattern** is a list of three websites (not necessarily distinct).

*   For example, `[ "home ", "away ", "love "]`, `[ "leetcode ", "love ", "leetcode "]`, and `[ "luffy ", "luffy ", "luffy "]` are all patterns.

The **score** of a **pattern** is the number of users that visited all the websites in the pattern in the same order they appeared in the pattern.

*   For example, if the pattern is `[ "home ", "away ", "love "]`, the score is the number of users `x` such that `x` visited `"home "` then visited `"away "` and visited `"love "` after that.
*   Similarly, if the pattern is `[ "leetcode ", "love ", "leetcode "]`, the score is the number of users `x` such that `x` visited `"leetcode "` then visited `"love "` and visited `"leetcode "` **one more time** after that.
*   Also, if the pattern is `[ "luffy ", "luffy ", "luffy "]`, the score is the number of users `x` such that `x` visited `"luffy "` three different times at different timestamps.

Return _the **pattern** with the largest **score**_. If there is more than one pattern with the same largest score, return the lexicographically smallest such pattern.

**Example 1:**

**Input:** username = \[ "joe ", "joe ", "joe ", "james ", "james ", "james ", "james ", "mary ", "mary ", "mary "\], timestamp = \[1,2,3,4,5,6,7,8,9,10\], website = \[ "home ", "about ", "career ", "home ", "cart ", "maps ", "home ", "home ", "about ", "career "\]
**Output:** \[ "home ", "about ", "career "\]
**Explanation:** The tuples in this example are:
\[ "joe ", "home ",1\],\[ "joe ", "about ",2\],\[ "joe ", "career ",3\],\[ "james ", "home ",4\],\[ "james ", "cart ",5\],\[ "james ", "maps ",6\],\[ "james ", "home ",7\],\[ "mary ", "home ",8\],\[ "mary ", "about ",9\], and \[ "mary ", "career ",10\].
The pattern ( "home ",  "about ",  "career ") has score 2 (joe and mary).
The pattern ( "home ",  "cart ",  "maps ") has score 1 (james).
The pattern ( "home ",  "cart ",  "home ") has score 1 (james).
The pattern ( "home ",  "maps ",  "home ") has score 1 (james).
The pattern ( "cart ",  "maps ",  "home ") has score 1 (james).
The pattern ( "home ",  "home ",  "home ") has score 0 (no user visited home 3 times).

**Example 2:**

**Input:** username = \[ "ua ", "ua ", "ua ", "ub ", "ub ", "ub "\], timestamp = \[1,2,3,4,5,6\], website = \[ "a ", "b ", "a ", "a ", "b ", "c "\]
**Output:** \[ "a ", "b ", "a "\]

**Constraints:**

*   `3 <= username.length <= 50`
*   `1 <= username[i].length <= 10`
*   `timestamp.length == username.length`
*   `1 <= timestamp[i] <= 109`
*   `website.length == username.length`
*   `1 <= website[i].length <= 10`
*   `username[i]` and `website[i]` consist of lowercase English letters.
*   It is guaranteed that there is at least one user who visited at least three websites.
*   All the tuples `[username[i], timestamp[i], website[i]]` are **unique**.
String Transforms Into Another String

Given two strings `str1` and `str2` of the same length, determine whether you can transform `str1` into `str2` by doing **zero or more** _conversions_.

In one conversion you can convert **all** occurrences of one character in `str1` to **any** other lowercase English character.

Return `true` if and only if you can transform `str1` into `str2`.

**Example 1:**

**Input:** str1 =  "aabcc ", str2 =  "ccdee "
**Output:** true
**Explanation:** Convert 'c' to 'e' then 'b' to 'd' then 'a' to 'c'. Note that the order of conversions matter.

**Example 2:**

**Input:** str1 =  "leetcode ", str2 =  "codeleet "
**Output:** false
**Explanation:** There is no way to transform str1 to str2.

**Constraints:**

*   `1 <= str1.length == str2.length <= 104`
*   `str1` and `str2` contain only lowercase English letters.
Day of the Year

Given a string `date` representing a [Gregorian calendar](https://en.wikipedia.org/wiki/Gregorian_calendar) date formatted as `YYYY-MM-DD`, return _the day number of the year_.

**Example 1:**

**Input:** date =  "2019-01-09 "
**Output:** 9
**Explanation:** Given date is the 9th day of the year in 2019.

**Example 2:**

**Input:** date =  "2019-02-10 "
**Output:** 41

**Constraints:**

*   `date.length == 10`
*   `date[4] == date[7] == '-'`, and all other `date[i]`'s are digits
*   `date` represents a calendar date between Jan 1st, 1900 and Dec 31th, 2019.
Number of Dice Rolls With Target Sum

You have `n` dice, and each die has `k` faces numbered from `1` to `k`.

Given three integers `n`, `k`, and `target`, return _the number of possible ways (out of the_ `kn` _total ways)_ _to roll the dice, so the sum of the face-up numbers equals_ `target`. Since the answer may be too large, return it **modulo** `109 + 7`.

**Example 1:**

**Input:** n = 1, k = 6, target = 3
**Output:** 1
**Explanation:** You throw one die with 6 faces.
There is only one way to get a sum of 3.

**Example 2:**

**Input:** n = 2, k = 6, target = 7
**Output:** 6
**Explanation:** You throw two dice, each with 6 faces.
There are 6 ways to get a sum of 7: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1.

**Example 3:**

**Input:** n = 30, k = 30, target = 500
**Output:** 222616187
**Explanation:** The answer must be returned modulo 109 + 7.

**Constraints:**

*   `1 <= n, k <= 30`
*   `1 <= target <= 1000`
Swap For Longest Repeated Character Substring

You are given a string `text`. You can swap two of the characters in the `text`.

Return _the length of the longest substring with repeated characters_.

**Example 1:**

**Input:** text =  "ababa "
**Output:** 3
**Explanation:** We can swap the first 'b' with the last 'a', or the last 'b' with the first 'a'. Then, the longest repeated character substring is  "aaa " with length 3.

**Example 2:**

**Input:** text =  "aaabaaa "
**Output:** 6
**Explanation:** Swap 'b' with the last 'a' (or the first 'a'), and we get longest repeated character substring  "aaaaaa " with length 6.

**Example 3:**

**Input:** text =  "aaaaa "
**Output:** 5
**Explanation:** No need to swap, longest repeated character substring is  "aaaaa " with length is 5.

**Constraints:**

*   `1 <= text.length <= 2 * 104`
*   `text` consist of lowercase English characters only.
Online Majority Element In Subarray

Design a data structure that efficiently finds the **majority element** of a given subarray.

The **majority element** of a subarray is an element that occurs `threshold` times or more in the subarray.

Implementing the `MajorityChecker` class:

*   `MajorityChecker(int[] arr)` Initializes the instance of the class with the given array `arr`.
*   `int query(int left, int right, int threshold)` returns the element in the subarray `arr[left...right]` that occurs at least `threshold` times, or `-1` if no such element exists.

**Example 1:**

**Input**
\[ "MajorityChecker ",  "query ",  "query ",  "query "\]
\[\[\[1, 1, 2, 2, 1, 1\]\], \[0, 5, 4\], \[0, 3, 3\], \[2, 3, 2\]\]
**Output**
\[null, 1, -1, 2\]

**Explanation**
MajorityChecker majorityChecker = new MajorityChecker(\[1, 1, 2, 2, 1, 1\]);
majorityChecker.query(0, 5, 4); // return 1
majorityChecker.query(0, 3, 3); // return -1
majorityChecker.query(2, 3, 2); // return 2

**Constraints:**

*   `1 <= arr.length <= 2 * 104`
*   `1 <= arr[i] <= 2 * 104`
*   `0 <= left <= right < arr.length`
*   `threshold <= right - left + 1`
*   `2 * threshold > right - left + 1`
*   At most `104` calls will be made to `query`.
Find Words That Can Be Formed by Characters

You are given an array of strings `words` and a string `chars`.

A string is **good** if it can be formed by characters from chars (each character can only be used once).

Return _the sum of lengths of all good strings in words_.

**Example 1:**

**Input:** words = \[ "cat ", "bt ", "hat ", "tree "\], chars =  "atach "
**Output:** 6
**Explanation:** The strings that can be formed are  "cat " and  "hat " so the answer is 3 + 3 = 6.

**Example 2:**

**Input:** words = \[ "hello ", "world ", "leetcode "\], chars =  "welldonehoneyr "
**Output:** 10
**Explanation:** The strings that can be formed are  "hello " and  "world " so the answer is 5 + 5 = 10.

**Constraints:**

*   `1 <= words.length <= 1000`
*   `1 <= words[i].length, chars.length <= 100`
*   `words[i]` and `chars` consist of lowercase English letters.
Maximum Level Sum of a Binary Tree

Given the `root` of a binary tree, the level of its root is `1`, the level of its children is `2`, and so on.

Return the **smallest** level `x` such that the sum of all the values of nodes at level `x` is **maximal**.

**Example 1:**

**Input:** root = \[1,7,0,7,-8,null,null\]
**Output:** 2
**Explanation:** 
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.

**Example 2:**

**Input:** root = \[989,null,10250,98693,-89388,null,null,null,-32127\]
**Output:** 2

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 104]`.
*   `-105 <= Node.val <= 105`
As Far from Land as Possible

Given an `n x n` `grid` containing only values `0` and `1`, where `0` represents water and `1` represents land, find a water cell such that its distance to the nearest land cell is maximized, and return the distance. If no land or water exists in the grid, return `-1`.

The distance used in this problem is the Manhattan distance: the distance between two cells `(x0, y0)` and `(x1, y1)` is `|x0 - x1| + |y0 - y1|`.

**Example 1:**

**Input:** grid = \[\[1,0,1\],\[0,0,0\],\[1,0,1\]\]
**Output:** 2
**Explanation:** The cell (1, 1) is as far as possible from all the land with distance 2.

**Example 2:**

**Input:** grid = \[\[1,0,0\],\[0,0,0\],\[0,0,0\]\]
**Output:** 4
**Explanation:** The cell (2, 2) is as far as possible from all the land with distance 4.

**Constraints:**

*   `n == grid.length`
*   `n == grid[i].length`
*   `1 <= n <= 100`
*   `grid[i][j]` is `0` or `1`
Last Substring in Lexicographical Order

Given a string `s`, return _the last substring of_ `s` _in lexicographical order_.

**Example 1:**

**Input:** s =  "abab "
**Output:**  "bab "
**Explanation:** The substrings are \[ "a ",  "ab ",  "aba ",  "abab ",  "b ",  "ba ",  "bab "\]. The lexicographically maximum substring is  "bab ".

**Example 2:**

**Input:** s =  "leetcode "
**Output:**  "tcode "

**Constraints:**

*   `1 <= s.length <= 4 * 105`
*   `s` contains only lowercase English letters.
Single-Row Keyboard

There is a special keyboard with **all keys in a single row**.

Given a string `keyboard` of length `26` indicating the layout of the keyboard (indexed from `0` to `25`). Initially, your finger is at index `0`. To type a character, you have to move your finger to the index of the desired character. The time taken to move your finger from index `i` to index `j` is `|i - j|`.

You want to type a string `word`. Write a function to calculate how much time it takes to type it with one finger.

**Example 1:**

**Input:** keyboard =  "abcdefghijklmnopqrstuvwxyz ", word =  "cba "
**Output:** 4
**Explanation:** The index moves from 0 to 2 to write 'c' then to 1 to write 'b' then to 0 again to write 'a'.
Total time = 2 + 1 + 1 = 4. 

**Example 2:**

**Input:** keyboard =  "pqrstuvwxyzabcdefghijklmno ", word =  "leetcode "
**Output:** 73

**Constraints:**

*   `keyboard.length == 26`
*   `keyboard` contains each English lowercase letter exactly once in some order.
*   `1 <= word.length <= 104`
*   `word[i]` is an English lowercase letter.
Design File System

You are asked to design a file system that allows you to create new paths and associate them with different values.

The format of a path is one or more concatenated strings of the form: `/` followed by one or more lowercase English letters. For example, "`/leetcode "` and "`/leetcode/problems "` are valid paths while an empty string `" "` and `"/ "` are not.

Implement the `FileSystem` class:

*   `bool createPath(string path, int value)` Creates a new `path` and associates a `value` to it if possible and returns `true`. Returns `false` if the path **already exists** or its parent path **doesn't exist**.
*   `int get(string path)` Returns the value associated with `path` or returns `-1` if the path doesn't exist.

**Example 1:**

**Input:** 
\[ "FileSystem ", "createPath ", "get "\]
\[\[\],\[ "/a ",1\],\[ "/a "\]\]
**Output:** 
\[null,true,1\]
**Explanation:** 
FileSystem fileSystem = new FileSystem();

fileSystem.createPath( "/a ", 1); // return true
fileSystem.get( "/a "); // return 1

**Example 2:**

**Input:** 
\[ "FileSystem ", "createPath ", "createPath ", "get ", "createPath ", "get "\]
\[\[\],\[ "/leet ",1\],\[ "/leet/code ",2\],\[ "/leet/code "\],\[ "/c/d ",1\],\[ "/c "\]\]
**Output:** 
\[null,true,true,2,false,-1\]
**Explanation:** 
FileSystem fileSystem = new FileSystem();

fileSystem.createPath( "/leet ", 1); // return true
fileSystem.createPath( "/leet/code ", 2); // return true
fileSystem.get( "/leet/code "); // return 2
fileSystem.createPath( "/c/d ", 1); // return false because the parent path  "/c " doesn't exist.
fileSystem.get( "/c "); // return -1 because this path doesn't exist.

**Constraints:**

*   `2 <= path.length <= 100`
*   `1 <= value <= 109`
*   Each `path` is **valid** and consists of lowercase English letters and `'/'`.
*   At most `104` calls **in total** will be made to `createPath` and `get`.
Minimum Cost to Connect Sticks

You have some number of sticks with positive integer lengths. These lengths are given as an array `sticks`, where `sticks[i]` is the length of the `ith` stick.

You can connect any two sticks of lengths `x` and `y` into one stick by paying a cost of `x + y`. You must connect all the sticks until there is only one stick remaining.

Return _the minimum cost of connecting all the given sticks into one stick in this way_.

**Example 1:**

**Input:** sticks = \[2,4,3\]
**Output:** 14
**Explanation:** You start with sticks = \[2,4,3\].
1. Combine sticks 2 and 3 for a cost of 2 + 3 = 5. Now you have sticks = \[5,4\].
2. Combine sticks 5 and 4 for a cost of 5 + 4 = 9. Now you have sticks = \[9\].
There is only one stick left, so you are done. The total cost is 5 + 9 = 14.

**Example 2:**

**Input:** sticks = \[1,8,3,5\]
**Output:** 30
**Explanation:** You start with sticks = \[1,8,3,5\].
1. Combine sticks 1 and 3 for a cost of 1 + 3 = 4. Now you have sticks = \[4,8,5\].
2. Combine sticks 4 and 5 for a cost of 4 + 5 = 9. Now you have sticks = \[9,8\].
3. Combine sticks 9 and 8 for a cost of 9 + 8 = 17. Now you have sticks = \[17\].
There is only one stick left, so you are done. The total cost is 4 + 9 + 17 = 30.

**Example 3:**

**Input:** sticks = \[5\]
**Output:** 0
**Explanation:** There is only one stick, so you don't need to do anything. The total cost is 0.

**Constraints:**

*   `1 <= sticks.length <= 104`
*   `1 <= sticks[i] <= 104`
Optimize Water Distribution in a Village

There are `n` houses in a village. We want to supply water for all the houses by building wells and laying pipes.

For each house `i`, we can either build a well inside it directly with cost `wells[i - 1]` (note the `-1` due to **0-indexing**), or pipe in water from another well to it. The costs to lay pipes between houses are given by the array `pipes` where each `pipes[j] = [house1j, house2j, costj]` represents the cost to connect `house1j` and `house2j` together using a pipe. Connections are bidirectional, and there could be multiple valid connections between the same two houses with different costs.

Return _the minimum total cost to supply water to all houses_.

**Example 1:**

**Input:** n = 3, wells = \[1,2,2\], pipes = \[\[1,2,1\],\[2,3,1\]\]
**Output:** 3
**Explanation:** The image shows the costs of connecting houses using pipes.
The best strategy is to build a well in the first house with cost 1 and connect the other houses to it with cost 2 so the total cost is 3.

**Example 2:**

**Input:** n = 2, wells = \[1,1\], pipes = \[\[1,2,1\],\[1,2,2\]\]
**Output:** 2
**Explanation:** We can supply water with cost two using one of the three options:
Option 1:
  - Build a well inside house 1 with cost 1.
  - Build a well inside house 2 with cost 1.
The total cost will be 2.
Option 2:
  - Build a well inside house 1 with cost 1.
  - Connect house 2 with house 1 with cost 1.
The total cost will be 2.
Option 3:
  - Build a well inside house 2 with cost 1.
  - Connect house 1 with house 2 with cost 1.
The total cost will be 2.
Note that we can connect houses 1 and 2 with cost 1 or with cost 2 but we will always choose **the cheapest option**. 

**Constraints:**

*   `2 <= n <= 104`
*   `wells.length == n`
*   `0 <= wells[i] <= 105`
*   `1 <= pipes.length <= 104`
*   `pipes[j].length == 3`
*   `1 <= house1j, house2j <= n`
*   `0 <= costj <= 105`
*   `house1j != house2j`
Invalid Transactions

A transaction is possibly invalid if:

*   the amount exceeds `$1000`, or;
*   if it occurs within (and including) `60` minutes of another transaction with the **same name** in a **different city**.

You are given an array of strings `transaction` where `transactions[i]` consists of comma-separated values representing the name, time (in minutes), amount, and city of the transaction.

Return a list of `transactions` that are possibly invalid. You may return the answer in **any order**.

**Example 1:**

**Input:** transactions = \[ "alice,20,800,mtv ", "alice,50,100,beijing "\]
**Output:** \[ "alice,20,800,mtv ", "alice,50,100,beijing "\]
**Explanation:** The first transaction is invalid because the second transaction occurs within a difference of 60 minutes, have the same name and is in a different city. Similarly the second one is invalid too.

**Example 2:**

**Input:** transactions = \[ "alice,20,800,mtv ", "alice,50,1200,mtv "\]
**Output:** \[ "alice,50,1200,mtv "\]

**Example 3:**

**Input:** transactions = \[ "alice,20,800,mtv ", "bob,50,1200,mtv "\]
**Output:** \[ "bob,50,1200,mtv "\]

**Constraints:**

*   `transactions.length <= 1000`
*   Each `transactions[i]` takes the form `"{name},{time},{amount},{city} "`
*   Each `{name}` and `{city}` consist of lowercase English letters, and have lengths between `1` and `10`.
*   Each `{time}` consist of digits, and represent an integer between `0` and `1000`.
*   Each `{amount}` consist of digits, and represent an integer between `0` and `2000`.
Compare Strings by Frequency of the Smallest Character

Let the function `f(s)` be the **frequency of the lexicographically smallest character** in a non-empty string `s`. For example, if `s = "dcce "` then `f(s) = 2` because the lexicographically smallest character is `'c'`, which has a frequency of 2.

You are given an array of strings `words` and another array of query strings `queries`. For each query `queries[i]`, count the **number of words** in `words` such that `f(queries[i])` < `f(W)` for each `W` in `words`.

Return _an integer array_ `answer`_, where each_ `answer[i]` _is the answer to the_ `ith` _query_.

**Example 1:**

**Input:** queries = \[ "cbd "\], words = \[ "zaaaz "\]
**Output:** \[1\]
**Explanation:** On the first query we have f( "cbd ") = 1, f( "zaaaz ") = 3 so f( "cbd ") < f( "zaaaz ").

**Example 2:**

**Input:** queries = \[ "bbb ", "cc "\], words = \[ "a ", "aa ", "aaa ", "aaaa "\]
**Output:** \[1,2\]
**Explanation:** On the first query only f( "bbb ") < f( "aaaa "). On the second query both f( "aaa ") and f( "aaaa ") are both > f( "cc ").

**Constraints:**

*   `1 <= queries.length <= 2000`
*   `1 <= words.length <= 2000`
*   `1 <= queries[i].length, words[i].length <= 10`
*   `queries[i][j]`, `words[i][j]` consist of lowercase English letters.
Remove Zero Sum Consecutive Nodes from Linked List

Given the `head` of a linked list, we repeatedly delete consecutive sequences of nodes that sum to `0` until there are no such sequences.

After doing so, return the head of the final linked list. You may return any such answer.

(Note that in the examples below, all sequences are serializations of `ListNode` objects.)

**Example 1:**

**Input:** head = \[1,2,-3,3,1\]
**Output:** \[3,1\]
**Note:** The answer \[1,2,1\] would also be accepted.

**Example 2:**

**Input:** head = \[1,2,3,-3,4\]
**Output:** \[1,2,4\]

**Example 3:**

**Input:** head = \[1,2,3,-3,-2\]
**Output:** \[1\]

**Constraints:**

*   The given linked list will contain between `1` and `1000` nodes.
*   Each node in the linked list has `-1000 <= node.val <= 1000`.
Dinner Plate Stacks

You have an infinite number of stacks arranged in a row and numbered (left to right) from `0`, each of the stacks has the same maximum capacity.

Implement the `DinnerPlates` class:

*   `DinnerPlates(int capacity)` Initializes the object with the maximum capacity of the stacks `capacity`.
*   `void push(int val)` Pushes the given integer `val` into the leftmost stack with a size less than `capacity`.
*   `int pop()` Returns the value at the top of the rightmost non-empty stack and removes it from that stack, and returns `-1` if all the stacks are empty.
*   `int popAtStack(int index)` Returns the value at the top of the stack with the given index `index` and removes it from that stack or returns `-1` if the stack with that given index is empty.

**Example 1:**

**Input**
\[ "DinnerPlates ",  "push ",  "push ",  "push ",  "push ",  "push ",  "popAtStack ",  "push ",  "push ",  "popAtStack ",  "popAtStack ",  "pop ",  "pop ",  "pop ",  "pop ",  "pop "\]
\[\[2\], \[1\], \[2\], \[3\], \[4\], \[5\], \[0\], \[20\], \[21\], \[0\], \[2\], \[\], \[\], \[\], \[\], \[\]\]
**Output**
\[null, null, null, null, null, null, 2, null, null, 20, 21, 5, 4, 3, 1, -1\]

**Explanation:** 
DinnerPlates D = DinnerPlates(2);  // Initialize with capacity = 2
D.push(1);
D.push(2);
D.push(3);
D.push(4);
D.push(5);         // The stacks are now:  2  4
                                           1  3  5
                                           ﹈ ﹈ ﹈
D.popAtStack(0);   // Returns 2.  The stacks are now:     4
                                                       1  3  5
                                                       ﹈ ﹈ ﹈
D.push(20);        // The stacks are now: 20  4
                                           1  3  5
                                           ﹈ ﹈ ﹈
D.push(21);        // The stacks are now: 20  4 21
                                           1  3  5
                                           ﹈ ﹈ ﹈
D.popAtStack(0);   // Returns 20.  The stacks are now:     4 21
                                                        1  3  5
                                                        ﹈ ﹈ ﹈
D.popAtStack(2);   // Returns 21.  The stacks are now:     4
                                                        1  3  5
                                                        ﹈ ﹈ ﹈ 
D.pop()            // Returns 5.  The stacks are now:      4
                                                        1  3 
                                                        ﹈ ﹈  
D.pop()            // Returns 4.  The stacks are now:   1  3 
                                                        ﹈ ﹈   
D.pop()            // Returns 3.  The stacks are now:   1 
                                                        ﹈   
D.pop()            // Returns 1.  There are no stacks.
D.pop()            // Returns -1.  There are still no stacks.

**Constraints:**

*   `1 <= capacity <= 2 * 104`
*   `1 <= val <= 2 * 104`
*   `0 <= index <= 105`
*   At most `2 * 105` calls will be made to `push`, `pop`, and `popAtStack`.
Prime Arrangements

Return the number of permutations of 1 to `n` so that prime numbers are at prime indices (1-indexed.)

_(Recall that an integer is prime if and only if it is greater than 1, and cannot be written as a product of two positive integers both smaller than it.)_

Since the answer may be large, return the answer **modulo `10^9 + 7`**.

**Example 1:**

**Input:** n = 5
**Output:** 12
**Explanation:** For example \[1,2,5,4,3\] is a valid permutation, but \[5,2,3,4,1\] is not because the prime number 5 is at index 1.

**Example 2:**

**Input:** n = 100
**Output:** 682289015

**Constraints:**

*   `1 <= n <= 100`