John uses a cutter to cut a rectangle of size MxN (N, M integer ≤ 5000) into a number of at least square dimensions of positive integers and have sides parallel to the original rectangular edge. The cutting cutter always cuts in parallel with one of the two sides of the rectangle and divides the rectangle into two parts. Calculate the number of squares created.

For example, with M = 5 and N = 6, the minimum number of squares that can be generated is 5.

We define some symmetries as if we read from right to left or vice versa, the same results were obtained. example: 121,78987, ... Some S have length k defined as supersymmetric numbers if the following conditions are satisfied: -S (1, k) is symmetrical -S (1, | k / 2 |) is symmetrical -S (k- | k / 2 | + 1, k) is symmetrical Here we define | x | is the largest integer that does not exceed x and S (a, b) is the number composed of a to b of S.. for example the numbers: 0.11,22322, ... are the super lie numbers. some close to supersymmetry (the first digit is always different from 0) is defined as if we could change the position of some numbers to make that number a supersymmetric number (note: after changing If the position is zero, it may still be considered the supersymmetric number) For example: 8404000 -> 040840 is some supersymmetric. Of course, some supersymmetry is some close to super lie Give 2 numbers l and r. Find out how many numbers are close to supersymmetry from l to r. with 1 <= l <= r <= 10e50000. Get the search results and get the remainder for 1e9 + 7. For example: l = 3111120 and r = 3111125. The result will be 2 (2 numbers near the supersymmetry are 3111122 and 3111123)

Give integer ranges A1, A2, .., AN. Number Ai is called the K-random number of the sequence if in K terms Any sequence of a sequence has at least one term equal to Ai and K is the smallest integer that satisfies this condition. Example: Range 1,2,3,1,2,2. Number 1 is a 3-random number; number 2 is a 3-random number; number 3 is a 4-random number Conditions: N <= 100000 and | Ai | <= 1000.

I need help with a problem like this: Count the number of arrays of n elements in which each element of the array has the value of paragraph [1, M] so that there are the same K consecutive values. with n, M, K <= 1000000 For example: n = 3, M = 2, k = 2 The result will be 6 satisfying fields that are (1,1,1); (1,1,2); (1,2,2); (2,1,1); (2,2,1); (2,2,2)