We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

- Prepare
- Algorithms
- Dynamic Programming
- Xor and Sum

# Xor and Sum

# Xor and Sum

You are given two positive integers and in binary representation. You should find the following sum modulo :

where operation means exclusive OR operation, operation means binary shift to the left.

Please note, that we consider ideal model of binary integers. That is there is infinite number of bits in each number, and there are no disappearings (or cyclic shifts) of bits.

**Input Format**

The first line contains number in binary representation. The second line contains number in the same format. All the numbers do not contain leading zeros.

**Output Format**

Output a single integer the required sum modulo .

**Sample Input**

```
10
1010
```

**Sample Output**

```
489429555
```