- All Contests
- ProjectEuler+
- Project Euler #238: Infinite string tour

# Project Euler #238: Infinite string tour

# Project Euler #238: Infinite string tour

_{This problem is a programming version of Problem 238 from projecteuler.net}

Create a sequence of numbers using the pseudo-random number generator:

Concatenate these numbers â€‰ to create a string of infinite length.

Then,

For a positive integer , if no substring of exists with a sum of digits equal to , is defined to be zero. If at least one substring of exists with a sum of digits equal to , we define , where is the starting position of the earliest such substring. **The string is -based indexed**.

For instance:

The substrings "", "" and "" with respective sums of digits equal to , and start at position , hence .

The substrings "" and "" with respective sums of digits equal to and start at position , hence . Note that the substring "" starting at position , has a sum of digits equal to , but there was an earlier substring (starting at position ) with a sum of digits equal to , so , not .

Let .

Given two integers and , find modulo .

**Input Format**

The only line of each test file contains two space-separated integers and .

**Constraints**

- .
- .
- The time limit is the double of the usual time limit.

**Output Format**

Print a single integer denoting modulo .

**Sample Input 0**

```
0 10
```

**Sample Output 0**

```
38
```

**Sample Input 1**

```
1 8
```

**Sample Output 1**

```
64
```

**Sample Input 2**

```
2 100
```

**Sample Output 2**

```
2035208
```

**Sample Input 3**

```
100000 1000000000000000000
```

**Sample Output 3**

```
57752062
```